如何使用C++中的Floyd-Warshall算法

如何使用C++中的Floyd-Warshall算法

Floyd-Warshall算法是一种用于求解有向加权图中所有节点对之间最短路径的算法。它采用动态规划的思想，通过不断更新节点对之间的距离信息，最终得出最短路径（即最小权重）。

在C++中，可以使用邻接矩阵（Adjacency Matrix）来表示图的结构，并通过Floyd-Warshall算法来求解最短路径。

邻接矩阵是一个二维数组，其中记录了每个节点之间的权重（距离）。若两个节点之间没有直接连接，则用一个较大的数（如无穷大）表示。

立即学习“C++免费学习笔记（深入）”；

下面是一个示例代码，展示如何使用C++中的Floyd-Warshall算法：

动态WEB网站中的PHP和MySQL：直观的QuickPro指南第2版

动态WEB网站中的PHP和MySQL详细反映实际程序的需求，仔细地探讨外部数据的验证(例如信用卡卡号的格式)、用户登录以及如何使用模板建立网页的标准外观。动态WEB网站中的PHP和MySQL的内容不仅仅是这些。书中还提到如何串联JavaScript与PHP让用户操作时更快、更方便。还有正确处理用户输入错误的方法，让网站看起来更专业。另外还引入大量来自PEAR外挂函数库的强大功能，对常用的、强大的包

下载

#include 
using namespace std;

const int INF = 1e9; // 无穷大

void floydWarshall(int graph[][4], int n) {
    int dist[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = graph[i][j];
        }
    }
  
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 输出最短路径矩阵
    cout << "最短路径矩阵：" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INF) {
                cout << "INF" << "    ";
            } else {
                cout << dist[i][j] << "    ";
            }
        }
        cout << endl;
    }
}

int main() {
    int graph[4][4] = { {0, 5, INF, 10},
                        {INF, 0, 3, INF},
                        {INF, INF, 0, 1},
                        {INF, INF, INF, 0} };

    floydWarshall(graph, 4);

    return 0;
}

以上代码中，我们定义了一个4x4的邻接矩阵graph，并用INF表示不存在的边。然后，调用floydWarshall函数，传入图和节点数目。函数中，我们使用dist二维数组保存当前节点对之间的最短路径信息。

在Floyd-Warshall算法的主循环中，我们不断更新dist数组，直到得到最终的最短路径矩阵。最后，我们输出最短路径矩阵，将INF替换成无穷大，便于阅读。

请注意，由于Floyd-Warshall算法的时间复杂度为O(n^3)，其中n为节点数目，因此对于大规模的图，算法可能会运行较慢。

希望这篇文章能够对你理解和使用C++中的Floyd-Warshall算法有所帮助。