本文共 985 字，大约阅读时间需要 3 分钟。
floyd算法：求多个顶点到多个顶点的最短路径。
算法核心思想: 将每一个顶点v作为中间节点，在任意两个顶点对i，j之间，判断i，j之间的距离，经过顶点v是否更小，是，则更新距离和路径。
算法的时间复杂度为O(n³)
用两个二维数组来记录，顶点与顶点之间的距离和路径
dist[][]用来记录两个顶点之间的距离，例如dist[i][j]的值，就是顶点i到顶点j之间的距离
path[][]用来记录两个顶点之间的路径，例如path[i][j]的值，就是顶点i到顶点j要经过的路径
对于 dist[i][j] > dist[i][k] + dist[k][j] 来说，如果k = i，那么dist[i][j] = dist[i][i] + dist[i][j],这个判断就没有意义了 如果k=j，i=j，同样如此，所以不做判断，直接跳过。
int dist[MAXVERTEX][MAXVERTEX], path[MAXVERTEX][MAXVERTEX];//图是以矩阵存储的void Floyd(Graph G) { int i, j, k; for (i = 0; i < G->Nv;i++) { for (j = 0; j < G->Nv; j++) { //初始dist，path数组 dist[i][j] = G->Graph[i][j]; path[i][j] = -1; } } for (k = 0; k < G->Nv; k++) { //以每一个顶点k作为中间点 for (i = 0; i < G->Nv; i++) { if (k == i) { continue; } for (j = 0; j < G->Nv; j++) { //对于任意一对顶点i，j，如果i，j，通过中间的k的距离更小，则更新距离和路径 if (k == j||i == j) { continue; } if (dist[i][j] > dist[i][k] + dist[k][j]) { dist[i][j] = dist[i][k] + dist[k][j]; path[i][j] = k; } } } }} 转载地址：http://pqyo.baihongyu.com/