|
假设 N=(V,{E})是连通网，V是顶点集合，共有n个顶点； 对“最短路径“的两个理解： case-1，顶点V0到其它所有顶点的最短路径。 case-2，顶点V0到顶点Vi的最短路径。
对于Dijkstra算法来说，一次性求出V0到其它所有顶点的最短路径的时间复杂度是O(n^2). Dijkstra算法采用贪心思想，从V0出发，层层向外扩散，一步步求出V0到Vi之间所有顶点的最短路径，最终求得了V0～Vi的最短路径。 也就是说，极端情况下，case-1和case-2的循环次数是完全一致的；大多数情况下，case-2要比case-1的循环次数要少；case-1和case-2共享同一种算法，只不过在算法循环过程中，当我们发现已经找出V0～Vi的最短路径后，跳出循环即为case-2，继续循环即为case-1。
Dijkstra算法的输入变量、输出变量、辅助变量分别如下： 输入变量： 图（顶点集+边集，可用邻接矩阵也可用双重链表） 辅助变量： int final[MAXVEX]：标志位数组，final[i]=1表示V0-Vi的最短路径已经求得。 输出变量： 两个数组，分别是存储顶点下标的数组PrevV[MAXVEX]，以及存储最短路径长度的数组ShortPath[MAXVEX]。 PrevV[MAXVEX]：PrevV[i]=m的含义是，顶点V0到顶点Vi的最短路径的前置顶点是Vm，也就是，该最短路径为： V0--->...--->Vm--->Vi 有了PrevV[]，也就有了最短路径树。 ShortPath[MAXVEX]：ShortPath[i]=L的含义是，顶点V0到顶点Vi的最短路径长度是L。注意，算法运行过程中，该数组会被不断修正，直到final[i]=1;
算法的思路： 对于连通网N=(V, {E})，定义顶点集S为已经找到最短路径的顶点集合，顶点集U为尚未找出最短路径的顶点集合。D[v0, i]表示v0到i的当前最短路径长度，W[i,j]表示i与j的边长。D是路径长度，W是相邻顶点组成的边长。用集合P来表示v0到各顶点最短路径的前置顶点。 初始状态：S={v0}, U=V-S；（用final数组来存储S与U） 从U中选取一个距离v0的路径最短的顶点k，把k加入S；伪代码： min = MAX; for(j in U){ if(D[v0, j] < min){ min = D[v0, j]; k = j; } } final[k] = 1;//表示将k加入到S中 以k做为途经点，修正v0到U中的与k相邻的各顶点的最短距离，也就是说，如果路径v0->...->k->j的长度比路径v0->...->j的原“最短“长度D[v0,j]更短，则取v0->...->k->j作为v0->..->j的最新最短路径。伪代码： for(j in NeighboursOf(k)){ if(D[v0, k] + W[k, j] < D[v0, j]){ D[v0, j] = D[v0, k] + W[k, j]; //修正v0到j的最短路径长度 P[j] = k; //表示将j的前置顶点设为k，也就是将v0到j的最短路径修正为v0->...->k->j } }
算法伪代码： /* 计算v0到其它各顶点的最短路径 */ void MinPath_Dijkstra(Graph g, int v0) { int short_path[MAXVEX]; //存储v0到其它各顶点的最短路径长度 int prev_v[MAXVEX];//存储v0到其它各顶点最短路径经过的前置顶点 int final[MAXVEX]; //标记v0到某顶点是否已经找出最短路径 int j = 0; int k = 0; for(j = 0; j<MAXVEX; j++){ //初始化 final[j] = 0; short_path[j] = g[v0][j]; //将v0的所有边加入，g[v0][j]表示边长，如果边<v0, j>不存在，则设为无限大 prev_v[j] = 0; } final[v0] = 1; //直接将v0纳入已找到最短路径的顶点集 short_path[v0] = 0; //<v0, v0>不存在 for(i = 1; i < MAXVEX; i++){ //最外层循环，表示一共需要找出MAXVEX-1条最短路径 min = MAX; k = 0; for(j=0; j<MAXVEX; j++){ //本循环的目的是找出从v0到剩余顶点（final[j]==0）中最短的一条路径 if(final[j]==0 && short_path[j]<min){ min = short_path[j]; k = j; } } final[k] = 1; //表示v0到k的最短路径已找到 for(j=0; j<MAXVEX; j++){ /* v0到其它各顶点（尚未确定最短路径的顶点）的最短路径中，如果途经顶点k的路径长度比原路径更短,就更新。 此处min是v0到k的最短路径，g[k][j]是边<k,j>的长度，short_path[j]是v0到j的最短路径。 也就是说，如果路径 v0--->...--->k--->j 的长度比 v0--->...--->j 更短，则修正v0到j的最短路 径，将k设置为这条路径上顶点j的前置顶点 */ if(final[j]==0 && min+g[k][j] < short_path[j]){ short_path[j] = min+g[k][j]; prev_v[j] = k; } } } }
| 
转播
