最短路径——迪杰斯特拉与弗洛伊德算法

一.迪杰斯特拉算法

首先对于最短路径来说：从vi-vj的最短路径，不用非要经过所有的顶点，只需要找到路径最短的路径即可；

那么迪杰斯特拉的算法：其实也就与最小生成树的思想类似，找到较小的，然后更新；

首先将dist（路径）长度初始化为两个点之间边的权值，而如果不能一次到达，就是INIFINITY

而迪杰斯特拉算法就是：加点，如果加上中转点之后，再判断此时的最短路径长度，如果此时i-j-k的路径长度小于i-k的，那么此时顶点vi的最短路径就修改为中转路径长度；并且最终将找到的最小路径的终点加入到集合S中，直至所有的顶点都在S中就找到了V0到所有其他顶点的最短路径；

就是判断，更新，但最中间的过程有点麻烦，条件判断也太多；像比于书中的用链表来表示集合的加点，加边，还是实验题中的利用标志数组更为容易，将标志数组变为0/1，这样就不用那么麻烦！！！

下面给出关于迪杰斯特拉算法的完整代码：

#define MAX_VERTEX_NUM 100
#define INFINITY 32768//表示极大值typedef struct
{int vex1;int vex2;int adj_weight;
}Arc;typedef int VertexData;typedef struct ArcNode
{int adj;
}ArcNode;typedef struct
{VertexData vertex[MAX_VERTEX_NUM];ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int vexnum, arcnum;
}AdjMatrix;//邻接矩阵创建有向图
void CreateDN(AdjMatrix* G,int m)
{int i; int j;int** arr = (int**)malloc(m* sizeof(int*));for (i = 0; i <m; i++){arr[i] = (int*)malloc(m* sizeof(int));}for (i = 0; i < m; i++){for (j = 0; j < m; j++){scanf("%d", &arr[i][j]);}}for (i = 0; i < m; i++){for (j = 0; j <m; j++){if (arr[i][j] != 0){G->arcs[i][j].adj = arr[i][j];}else{G->arcs[i][j].adj = INFINITY;}}}G->vexnum = m;for (i = 0; i <m; i++){free(arr[i]);}free(arr);
}void PrintAdj(AdjMatrix* G)
{for (int i = 0; i <G->vexnum; i++){for (int j = 0; j < G->vexnum; j++){printf("%d ", G->arcs[i][j].adj);}printf("\n");}
}typedef int** PathMatrix;
typedef int* ShortPathTable;
//第五题//path用于保存路径信息，dist用来表示最短路径长度，即边的权值
void ShortestPath_DIJ(AdjMatrix* G, int v0, PathMatrix P, ShortPathTable D)
{int i = 0, j, w, v, min;int final[MAX_VERTEX_NUM];for (v = 0; v < G->vexnum; v++){final[v] = 0;D[v] = G->arcs[v0][v].adj;//从源点到点v的距离,for (w = 0; w < G->vexnum; w++){P[v][w] = 0;//从源点到w点的最短路径是否经过v点//到所有点都设置为不可到达？设置空路径}if (D[v] < INFINITY)//那么初始化的时候，要再加一个附加条件，如果矩阵输入为0，则INFINITY{P[v][v0] = 1; P[v][v] = 1;//小于的话，就存在直接到达的路径//那为什么还要经过v？为什么P？？？对于矩阵P的意义还是没理解}//从源点到顶点v0中v是中间要经过的}D[v0] = 0;//v0到v0的距离为0；final[v0] = 1;//到自身肯定已经遍历完成//for (i = 1; i < G->vexnum; i++)//这里只代表循环次数，i没有实际的意义//表示剩余的n-1个节点{min = INFINITY;for (w = 0; w < G->vexnum; w++)//有的可能从源点到达不了w，所以一直循环//此时一直循环：{if (!final[w])//说明还没有找到从源点到w的路径{if (D[w] < min){v = w;//此时将v更新为w（不要只注意前两行的,还有后面的//为什么要更新为w呢？//此时v在第一步肯定是要更新的，//然后v就是代表除了v0以外的节点，那么此时也就是从v0到v的已经找到路径min = D[w];}}}//上述过程就是在找到剩下的节点中到达v0的最小的距离final[v] = 1;//见上面的解释//此时就是最终的v才是最后真正访问的w//将final[v]更新以后，他就不再参与后面的运算！就不会与min进行比较//那么就是找出剩余的最短的路径——这就体现了按照路径长度递增的次序for (w = 0; w < G->vexnum; w++){if (!final[w] && (min + G->arcs[v][w].adj) < D[w])//说明找到了//一个更短的路径,这个才是更新路径的判断条件{D[w] = min + G->arcs[v][w].adj;//更新最短路径for (j = 0; j < G->vexnum; j++){P[w][j] = P[v][j];//P有什么用？？?}P[w][w] = 1;//说明已经完成了所有的遍历？因为在循环中，所有的都设置为1了}}}for (i = 0; i < G->vexnum; i++){if (i != v0){if (D[i] < INFINITY){printf("%d ", D[i]);}else{printf("-1 ");}}}
}int main()
{AdjMatrix G;//G = (AdjMatrix*)malloc(sizeof(AdjMatrix));int m, n;scanf("%d %d",&m, &n);CreateDN(&G, m);//PrintAdj(G);PathMatrix p;p = (int**)malloc(G.vexnum*sizeof(int*));for (int i = 0; i < m; i++){p[i] = (int*)calloc(G.vexnum,sizeof(int));}ShortPathTable D;D = (int*)malloc(m*sizeof(int));for (int i = 0; i <m; i++){D[i] =INFINITY;}//别忘了把n加1；ShortestPath_DIJ(&G, n, p, D);return 0;
}

二.弗洛伊德算法

若是求任意两个顶点之间的最短路径，就可以将每一个顶点作为源，多次调用迪杰斯特拉算法就可以找到任意两个顶点之间的最短路径，而利用弗洛伊德算法：就可以直接利用三重循环求出任意两点间的最短路径；

弗洛伊德算法最重要的就是要理解三重循环：

首先理解一下path：这个数组是存放i->j的最短路径的前驱结点，也就是距离j结点的最近的一个结点；

这时候：会有一个疑问，只存放一个前驱结点，那如何打印出路径上的所有结点呢？

有这个疑问就是没有理解三重循环的含义：假设i->j的前驱节点path[i][j]=p；

而p也是属于其他所有结点中的一个结点，那么自然也会有从i->p的最短路径，假设i->p的最短路径的前驱结点为m，那么i....m->p->j；也就是说，m也是属于从i->j的最短路径上的结点（因为单个值最小，所有的单个值的和肯定也最小，m,是保证从i->p的路径最短的点，那么m理应属于i->j的最短路径）以此类推直到找到距离i最近的前驱节点；此时也就找出了从顶点i到达任意所有其他结点的最小路径；而i->j的路径也就在这个过程中能够全部得出来！

综上所述：三层循环得本质我们就可以得到：i,j两层循环是作为二维数组的下标i,j；而表示从结点i到达结点j，而k则是可以作为前驱节点（中间结点）因为前驱节点肯定是在所有结点中间的，所以这层k的循环就代表这个意思；最终就能够找到所有的由顶点i到其他所有结点的最小路径；

而在打印路径的时候，根据上面的理解，path[i][j]只代表一个结点，那难道就只能打印一个结点吗？

根据上面的理解，我们既然可以找到i->j的前驱节点k，那么自然也能找到i->k的前驱结点，以此类推，递归下去，就能找到i->j的路上的所有其它的结点；

所以打印的过程是个递归的过程；