最短路径问题的经典解法-佛洛依德算法

问题描述：设计算法求解图的最短路径

【算法设计思想】

1. 初始化距离矩阵：首先，将解决方案矩阵 dist[][] 初始化为输入图矩阵 graph[][]，这个矩阵存储了顶点之间的直接距离或者权值。
2. 中间顶点迭代：然后，对每一个顶点作为中间顶点进行迭代。算法通过逐步考虑中间顶点，尝试找到更短的路径。
3. 源点和目标点迭代：对于每一对源点和目标点，算法尝试通过当前的中间顶点来缩短路径。
4. 更新最短路径：如果顶点 k 在顶点 i 和 j 之间的最短路径上，那么更新 dist[i][j]，使其成为新的最短路径。
5. 迭代完成：当所有的中间顶点都被考虑完毕时，算法结束，此时 dist[][] 中存储的就是所有顶点对之间的最短路径。
6. 打印最短路径矩阵：最后，打印出计算得到的最短路径矩阵，即图中所有顶点对之间的最短路径长度。

【算法描述】

// 实现Floyd Warshall算法
void floydWarshall(int graph[][V]) {
    // dist[][]将是输出数组，即最终的最短距离矩阵
    int dist[V][V], i, j, k;

    // 初始化解决方案矩阵，与输入图矩阵一样
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];

    // 添加所有顶点一个个作为中间顶点
    for (k = 0; k < V; k++) {
        // 选择所有顶点作为源点
        for (i = 0; i < V; i++) {
            // 选择所有顶点作为目标点，对于每个源点和目标点对
            for (j = 0; j < V; j++) {
                // 如果顶点k在i和j之间的最短路径上，则更新dist[i][j]
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }

    // 打印最短距离矩阵
    printSolution(dist);
}

【完整的测试程序】

#include <stdio.h>

// 定义无穷大，表示两点间无直接连接
#define INF 99999

// 顶点数
#define V 4

// 打印解决方案的函数
void printSolution(int dist[][V]);

// 实现Floyd Warshall算法
void floydWarshall(int graph[][V]) {
    // dist[][]将是输出数组，即最终的最短距离矩阵
    int dist[V][V], i, j, k;

    // 初始化解决方案矩阵，与输入图矩阵一样
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];

    // 添加所有顶点一个个作为中间顶点
    for (k = 0; k < V; k++) {
        // 选择所有顶点作为源点
        for (i = 0; i < V; i++) {
            // 选择所有顶点作为目标点，对于每个源点和目标点对
            for (j = 0; j < V; j++) {
                // 如果顶点k在i和j之间的最短路径上，则更新dist[i][j]
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }

    // 打印最短距离矩阵
    printSolution(dist);
}

void printSolution(int dist[][V]) {
    printf("以下矩阵显示所有点对之间的最短距离\n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF)
                printf("%7s", "INF");
            else
                printf("%7d", dist[i][j]);
        }
        printf("\n");
    }
}

int main() {
    /* 例子中的图的权重矩阵 */
    int graph[V][V] = {{0, 5, INF, 10},
                       {INF, 0, 3, INF},
                       {INF, INF, 0, 1},
                       {INF, INF, INF, 0}
                      };

    // 运行Floyd-Warshall算法
    floydWarshall(graph);
    return 0;
}