本文记录的是我对 最短路径算法的探索与理解。
最短路径算法在现实生活中也具有非常多的应用，例如在一个复杂的景区，想要从一个景点到另外一个景点，利用最短路径算法就可以找到最短的路程，而如果不做规划就随缘前往，可能会绕很多路才能到达，虽然到了，但是精力都花费在走路上了，更别说去观光景点了。
Dijkstra算法
算法基本思想
算法从某一点开始出发，向周围扩散，每次去寻找一个确定了最短路径的点，并且同时更新所有点的最短路径距离，并且在确认是最短路径点后更新该点的最短距离及其前驱节点，直到所有点都被找到最短路径。
算法代码：
#define MAX 100
#define INF 65535
int tempMatrix[MAX][MAX]; // 邻接矩阵
int mVexNum; // 顶点数量
void dijkstra(int start, int prev[], int dist[])
{
int i,j,k = 0;
int min;
int tmp;
int flag[MAX]; // flag[i] = 1 表示"顶点vs"到"顶点i"的最短路径已成功获取。
// 初始化
for (i = 0; i < mVexNum; i++)
{
flag[i] = 0; // 顶点i的最短路径还没获取到。
prev[i] = 0; // 顶点i的前驱顶点为0。
dist[i] = tempMatrix[start][i]; // 顶点i的最短路径为"顶点start"到"顶点i"的权。
}
// 对"顶点start"自身进行初始化
flag[start] = 1;
dist[start] = 0;
// 遍历mVexNum-1次；每次找出一个顶点的最短路径。
for (i = 1; i < mVexNum; i++)
{
// 寻找当前最小的路径；
// 即，在未获取最短路径的顶点中，找到离start最近的顶点(k)。
min = INF;
for (j = 0; j < mVexNum; j++)
{
if (flag[j] == 0 && dist[j] < min)
{
min = dist[j];
k = j;
}
}
// 标记"顶点k"为已经获取到最短路径
flag[k] = 1;
// 修正当前最短路径和前驱顶点
// 即，当已经知道"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
for (j = 0; j < mVexNum; j++)
{
tmp = (tempMatrix[k][j] == INF ? INF : (min + tempMatrix[k][j]));
if (flag[j] == 0 && (tmp < dist[j]))
{
dist[j] = tmp;
prev[j] = k;
}
}
}
}
细节分析：
算法中用到了三个数组，分别是：
- prev [ ]：用来存储每个节点的前驱节点
- dist [ ]：用来存储每个节点的最短路径距离
- flag [ ]：辅助数组，用来存储每个节点是否已经找到了最短路径
算法中用到了三次For循环，分别是：
第一次For：循环了N-1次，目的是每次循环都找到一个节点的最短路径
第二次For：循环了N次，目的是找到目前距离起始点最近的点，然后标记为已经找到最短路径
第三次For：循环了N次，由于新加入了一个确定了最短路径的节点，那么原来的节点的最短路径将有可能被更新，所以这个循环的目的就是更新所有的节点的最短路径的距离，如果发现了更短路径，同时也会将前驱节点更新。
