How to use shortest path algorithm in C++

How to use the shortest path algorithm in C

The shortest path algorithm is one of the key algorithms in graph theory. It is used to determine the shortest path between two vertices. path. In C language, many libraries are provided to implement shortest path algorithms, such as Dijkstra's algorithm and Floyd-Warshall algorithm. This article will give you a detailed introduction to how to use these two algorithms and provide corresponding code examples.

1. Dijkstra's algorithm

Dijkstra's algorithm is a greedy algorithm used to solve the single-source shortest path problem in weighted directed graphs. The following is a code example using C language to implement Dijkstra's algorithm:

#include <iostream>
#include <vector>
#include <queue>

const int INF = 1e9;

void dijkstraAlgorithm(int start, const std::vector<std::vector<std::pair<int, int>>>& graph, std::vector<int>& distance) {
    int n = graph.size();
    distance.resize(n, INF);
    distance[start] = 0;

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        int dist = pq.top().first;
        pq.pop();

        if (dist > distance[u]) {
            continue;
        }

        for (const auto& neighbor : graph[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;

            if (distance[u] + weight < distance[v]) {
                distance[v] = distance[u] + weight;
                pq.push({distance[v], v});
            }
        }
    }
}

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<std::pair<int, int>>> graph(n);

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }

    int start;
    std::cin >> start;

    std::vector<int> distance;
    dijkstraAlgorithm(start, graph, distance);

    for (int i = 0; i < n; ++i) {
        std::cout << "Distance from " << start << " to " << i << " is " << distance[i] << std::endl;
    }

    return 0;
}

The above code implements Dijkstra's algorithm. First, read the number of nodes n and the number of edges m of the graph from the input. Then, an adjacency list is created to represent the structure of the graph, and edge information is stored in the adjacency list. Next, read the starting node start. Finally, call the dijkstraAlgorithm function to calculate the shortest path from the starting node to other nodes and output the result.

2. Floyd-Warshall algorithm

Floyd-Warshall algorithm is used to solve the shortest path problem between all vertices in a weighted directed graph. The following is a code example using C language to implement the Floyd-Warshall algorithm:

#include <iostream>
#include <vector>

const int INF = 1e9;

void floydWarshallAlgorithm(const std::vector<std::vector<int>>& graph, std::vector<std::vector<int>>& distance) {
    int n = graph.size();

    distance = graph;

    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (distance[i][k] != INF && distance[k][j] != INF && distance[i][k] + distance[k][j] < distance[i][j]) {
                    distance[i][j] = distance[i][k] + distance[k][j];
                }
            }
        }
    }
}

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> graph(n, std::vector<int>(n, INF));

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        graph[u][v] = w;
    }

    std::vector<std::vector<int>> distance;
    floydWarshallAlgorithm(graph, distance);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (distance[i][j] == INF) {
                std::cout << "No path from " << i << " to " << j << std::endl;
            } else {
                std::cout << "Distance from " << i << " to " << j << " is " << distance[i][j] << std::endl;
            }
        }
    }

    return 0;
}

The above code implements the Floyd-Warshall algorithm. First, read the number of nodes n and the number of edges m of the graph from the input. Then, an adjacency matrix is ​​created to represent the structure of the graph, and the edge information is stored in the adjacency matrix. Finally, call the floydWarshallAlgorithm function to calculate the shortest path between all vertices and output the result.

Through the above code examples, you can learn how to use Dijkstra's algorithm and Floyd-Warshall algorithm in C to solve the shortest path problem. Hope this article will be helpful to you and increase your understanding of shortest path algorithm.

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