Cara menggunakan algoritma laluan terpendek dalam C++

Cara menggunakan algoritma laluan terpendek dalam C++

Algoritma laluan terpendek ialah salah satu algoritma utama dalam teori graf, yang digunakan untuk menentukan laluan terpendek antara dua bucu. Dalam bahasa C++, banyak perpustakaan disediakan untuk melaksanakan algoritma laluan terpendek, seperti algoritma Dijkstra dan algoritma Floyd-Warshall. Artikel ini akan memberi anda pengenalan terperinci tentang cara menggunakan kedua-dua algoritma ini dan memberikan contoh kod yang sepadan.

1. Algoritma Dijkstra

Algoritma Dijkstra ialah algoritma tamak yang digunakan untuk menyelesaikan masalah laluan terpendek sumber tunggal dalam graf berwajaran. Berikut ialah contoh kod yang menggunakan bahasa C++ untuk melaksanakan algoritma Dijkstra:

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

Kod di atas melaksanakan algoritma Dijkstra. Mula-mula, baca bilangan nod n dan bilangan tepi m graf daripada input. Kemudian, senarai bersebelahan dibuat untuk mewakili struktur graf dan maklumat tepi disimpan dalam senarai bersebelahan. Seterusnya, baca permulaan nod permulaan. Akhir sekali, panggil fungsi dijkstraAlgorithm untuk mengira laluan terpendek dari nod permulaan ke nod lain dan mengeluarkan hasilnya.

2. Algoritma Floyd-Warshall

Algoritma Floyd-Warshall digunakan untuk menyelesaikan masalah laluan terpendek antara semua bucu dalam graf berwajaran. Berikut ialah contoh kod yang menggunakan bahasa C++ untuk melaksanakan algoritma Floyd-Warshall:

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

Kod di atas melaksanakan algoritma Floyd-Warshall. Mula-mula, baca bilangan nod n dan bilangan tepi m graf daripada input. Kemudian, matriks bersebelahan dicipta untuk mewakili struktur graf, dan maklumat tepi disimpan dalam matriks bersebelahan. Akhir sekali, panggil fungsi floydWarshallAlgorithm untuk mengira laluan terpendek antara semua bucu dan mengeluarkan hasilnya.

Dengan contoh kod di atas, anda boleh belajar cara menggunakan algoritma Dijkstra dan algoritma Floyd-Warshall dalam C++ untuk menyelesaikan masalah laluan terpendek. Harap artikel ini akan membantu anda dan meningkatkan pemahaman anda tentang algoritma laluan terpendek.

Atas ialah kandungan terperinci Cara menggunakan algoritma laluan terpendek dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!