2017-11-22 10:28:42         来源：

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

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

```//created by getianao in 2017.11.21
#include
#include
using namespace std;
/*

*/
/*
@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);
}```