Floyd（弗洛伊德）算法 详解+模板

和Dijkstra算法一样，弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

基本思想

这里写图片描述

以上图G4为例，来对弗洛伊德进行算法演示。

图片描述

初始状态：S是记录各个顶点间最短路径的矩阵。

第1步：初始化S。

矩阵S中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞。实际上，就是将图的原始矩阵复制到S中。

注:a[i][j]表示矩阵S中顶点i(第i个顶点)到顶点j(第j个顶点)的距离。

第2步：以顶点A(第1个顶点)为中介点，若a[i][j] > a[i][0]+a[0][j]，则设置a[i][j]=a[i][0]+a[0][j]。

以顶点a[1]6，上一步操作之后，a[1][6]=∞；而将A作为中介点时，(B,A)=12，(A,G)=14，因此B和G之间的距离可以更新为26。

同理，依次将顶点B,C,D,E,F,G作为中介点，并更新a[i][j]的大小。

以”邻接矩阵”为例对弗洛伊德算法进行说明，对于”邻接表”实现的图在后面会给出相应的源码。

1. 基本定义

Graph是邻接矩阵对应的结构体。 vexs用于保存顶点，vexnum是顶点数，edgnum是边数；matrix则是用于保存矩阵信息的二维数组。例如，matrix[i][j]=1，则表示”顶点i(即vexs[i])”和”顶点j(即vexs[j])”是邻接点；matrix[i][j]=0，则表示它们不是邻接点。

2. 弗洛伊德算法

模板1 /* * floyd最短路径。 * 即，统计图中各个顶点间的最短路径。 * * 参数说明： * G – 图 * path – 路径。path[i][j]=k表示，”顶点i”到”顶点j”的最短路径会经过顶点k。 * dist – 长度数组。即，dist[i][j]=sum表示，”顶点i”到”顶点j”的最短路径的长度是svoid floyd(Graph G, int path[][MAX], int dist[][MAX]) { int i,j,k; int tmp; // 初始化 for (i = 0; i < G.vexnum; i++) { for (j = 0; j < G.vexnum; j++) { dist[i][j] = G.matrix[i][j]; // “顶点i”到”顶点j”的路径长度为”i到j的权值”。 path[i][j] = j; // “顶点i”到”顶点j”的最短路径是经过顶点j。 } }