图：单源点的最短路径问题dijkstra算法

单源点的最短路径问题：给定带权有向图G和源点v，求源点v到G中其余各顶点的最短路径；

中心思想：

①下一条最短路径或是从源点直接到终点，或是从源点通过已知的最短路径到达终点

②更新后，到剩余顶点的路径中最短的那条一定是到对应顶点的最短路径

//created by getianao in 2017.11.21
#include
#include
using namespace std;
/*
迪杰斯特拉算法解决了单元最短路径问题
时间复杂度是O(n^3)
*/
/*
@param x 从x到其他各顶点的最短路径
@param n 共有n个顶点
@param mastrix 带权有向图的邻接矩阵
*/

void dijkstra(int x, int n, int** mastrix)
{
	int i, j, k;
	int min;
	int* path = new int[n + 1];//储存到各节点最短路径的前驱
	int* mark = new int[n + 1];//标记是否已找出到该节点最短路径
	int* dist = new int[n + 1];//到各个顶点的最小路径长度
	//初始化
	for (int i = 1; i <= n; i++)
	{
		mark[i] = 0;//0表示未选择，1表示已选择
		dist[i] = mastrix[x-1][i-1];//直接到x的长度
		path[i] = x;//到x
	}
	mark[x] = 1;
	do {
		min = INT_MAX;
		k = 0;
		//找出到各个顶点的最短路径，这个值一定是到这个顶点的最小值，因为先到其他顶点长度更大
		for (int i = 1; i <= n; i++)
		{
			if (mark[i] != 1 && dist[i] < min)
			{
				min = dist[i];//min为到该顶点的最短路径
				k = i;
			}
		}
		if (k)//如果找到
		{
			mark[k] = 1;//标记已找到
			//检查是否能通过新选择出的最短路径来使到其他顶点路径长度变短
			for (int i = 1; i <= n; i++)
			{
				if (mastrix[k-1][i-1]min + mastrix[k-1][i-1])//新得出的x到该顶点的最短路径+该顶点到目标顶点
				{
					dist[i] = min + mastrix[k-1][i-1];
					path[i] = k;
				}
			}
		}
	} while (k);//所有点都已选出时k=0退出
	//打印各顶点最短路径
	for (int i = 1; i <= n; i++)
	{
		if (i != x&&dist[i] < INT_MAX)
		{
			k = i;
			do
			{
				cout << k << "<-";
				k = path[k];
			} while (k != x);
			cout << k << "  最短长度为:" << dist[i] << endl;;
		}
	}
}
int main()
{
	//测试
	int** mastrix=new int*[5];
	for (int i = 0; i<5; i++)
		mastrix[i] = new int[5];
	int a[5] = { 0,3,INT_MAX,INT_MAX ,30 };
	for (int i = 0; i < 5; i++)
		mastrix[0][i] = a[i];
	int b[5] = { INT_MAX,0,25,8,INT_MAX };
	for (int i = 0; i < 5; i++)
		mastrix[1][i] = b[i];
	int c[5] = { INT_MAX ,INT_MAX ,0,INT_MAX ,10 };
	for (int i = 0; i < 5; i++)
		mastrix[2][i] = c[i];
	int d[5] = { 20,INT_MAX ,4,0,12 };
	for (int i = 0; i < 5; i++)
		mastrix[3][i] = d[i];
	int e[5] = { 5,INT_MAX ,INT_MAX ,INT_MAX ,0 };
	for (int i = 0; i < 5; i++)
		mastrix[4][i] = e[i];
	dijkstra(1,5, mastrix);
}