How to use Floyd-Warshall algorithm in C++

How to use the Floyd-Warshall algorithm in C

The Floyd-Warshall algorithm is a method used to find the shortest path between all pairs of nodes in a directed weighted graph. algorithm. It adopts the idea of ​​dynamic programming and finally obtains the shortest path (i.e. minimum weight) by continuously updating the distance information between node pairs.

In C, you can use the adjacency matrix (Adjacency Matrix) to represent the structure of the graph, and solve the shortest path through the Floyd-Warshall algorithm.

The adjacency matrix is ​​a two-dimensional array that records the weight (distance) between each node. If there is no direct connection between two nodes, use a larger number (such as infinity) to represent it.

The following is a sample code showing how to use the Floyd-Warshall algorithm in C:

#include <iostream>
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;
}

In the above code, we define a 4x4 adjacency matrix graph, and use INF to indicate that it does not exist side. Then, call the floydWarshall function, passing in the graph and the number of nodes. In the function, we use the dist two-dimensional array to save the shortest path information between the current node pair.

In the main loop of the Floyd-Warshall algorithm, we continuously update the dist array until we get the final shortest path matrix. Finally, we output the shortest path matrix, replacing INF with infinity for easier reading.

Please note that since the time complexity of the Floyd-Warshall algorithm is O(n^3), where n is the number of nodes, the algorithm may run slower for large-scale graphs.

I hope this article can help you understand and use the Floyd-Warshall algorithm in C.

The above is the detailed content of How to use Floyd-Warshall algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!