数据结构_Floyd

用于求每一对顶点之间的最短路径问题

算法：Floyd
输入：带权有向图G=（V,E）
输出：每一对顶点的最短路径
        1.初始化：假设从Vi到Vj的弧是最短路径，即dist-1（Vi，Vj）=w
        2.循环变量k从0~n-1进行n次迭代：
            distk(Vi, Vj) = min{distk-1(Vi,Vj),distk-1(Vi,Vk)+distk-1(Vk,Vj)}

void Floyd() {int i, j, k, dist[MaxSize][MaxSize];for (i = 0; i < vertexNum; i++)for (j = 0; j < vertexNum; j++)dist[i][j] = edge[i][j];for (k = 0; k < vertexNum; k++)for (i = 0; i < vertexNum; i++)for (j = 0; j < vertexNum; j++)if (dist[i][k] + dist[k][j] < dist[i][j])dist[i][j] = dist[i][k] + dist[k][j];}

带path代码如下：

void Floyd() {int i, j, k, dist[MaxSize][MaxSize];String path[MaxSize][MaxSize];for (i = 0; i < vertexNum; i++)for (j = 0; j < vertexNum; j++){dist[i][j] = edge[i][j];if (dist[i][j] != 100)path[i][j] = vertex[i] + vertex[j];else path[i][j] = "";}for (k = 0; k < vertexNum; k++)for (i = 0; i < vertexNum; i++)for (j = 0; j < vertexNum; j++)if (dist[i][k] + dist[k][j] < dist[i][j]){dist[i][j] = dist[i][k] + dist[k][j];path[i][j] = path[i][k] + path[k][j];}}