Dijkstra的主要特点是以起始点为中心向外层层拓展（广度优先搜索思想），直到拓展到终点为止。
用二维数组edge表示顶点之间的关系，dis数组表示源点到其余各点的距离，book数组表示dis对应的距离是否是最短距离。
dis数组初始化为【0，2，6，4】，book为【1，0，0，0】
既然是求点1到其余各点的距离，那么，就找一个离点1最近的点。通过dis数组可知，为点2，这个图所有的边为正数，如果通过另一个点周转，必然大于点1到点2的距离。因此，book更新为【1，1，0，0】。然后，更新dis数组，查看是否有点经过点2周转之后，到达源点1的距离缩短了。发现dis[3] = 6, dis[2] + edge[2][3] = 5 < 6，dis更新为【0，2，5，4】（这个更新的过程叫“松弛”）重复上述的过程，第二轮迭代找到的点为点4，更新book为【1，1，0，1】，剩下的点3经过点4周转并不能缩小到源点的距离，因此，dis依然为【0，2，5，4】；第三轮迭代，确定点3，book更新为【1，1，1，1】，算法结束。
可以发现，每一轮迭代都可以确定一个点到源点的距离，因此，最多进行n-1次“松弛”，就可以结束算法。
算法图解，参考该博客：/heroacool/article/details/51014824
代码
#include <iostream>using namespace std;const int inf = 0x3f3f3f3f;int edge[5][5] = {{-1,-1,-1,-1,-1},{-1, 0, 2, 6, 4},{-1, inf, 0,3, inf},{-1, 7, inf, 0, 1},{-1, 5, inf, 12, 0}};int main() {const int n = 4;//点的数量int dis[n+1];//当前各点到源点的距离int book[n+1];//各点到源点是否为最小值//初始化，设源点为n1for (int i = 1; i <= n; ++i)dis[i] = edge[1][i];//book数组初始化memset(book, 0, sizeof(book));book[1] = 1;int min;//当前，未确定最短路径的点，到源点的最小距离大小//Dijkstra算法核心语句for (int i = 1; i <= n - 1; ++i) {//找到离1号顶点最近的顶点min = inf;int u;for (int j = 1; j <= n; ++j) {if (book[j] == 0 && dis[j] < min) {min = dis[j];u = j;}}//每轮迭代都可以确定一个点到源点的最短距离，因此只要迭代n-1轮book[u] = 1;//通过已经确定的点，对dis数组进行更新//（未确定的点通过点u，缩小了到源点的距离）for (int v = 1; v <= n; ++v) {if (edge[u][v] < inf) {if (dis[v] > dis[u] + edge[u][v])dis[v] = dis[u] + edge[u][v];}}}//输出结果for (int i = 1; i <= n; ++i)cout << dis[i] << ' ';system("pause");return 0;}
