Cara menggunakan algoritma Bellman-Ford dalam C++

Cara menggunakan algoritma Bellman-Ford dalam C++

Algoritma Bellman-Ford ialah algoritma yang digunakan untuk mencari laluan terpendek dari satu titik sumber ke semua bucu lain dalam graf. Ia boleh mengendalikan graf yang mengandungi tepi berat negatif, jadi ia digunakan secara meluas dalam penghalaan rangkaian, analisis pasaran kewangan dan bidang lain. Artikel ini akan memperkenalkan cara menggunakan algoritma Bellman-Ford dalam C++ dan memberikan contoh kod.

Idea teras algoritma Bellman-Ford adalah untuk terus mengemas kini anggaran laluan terpendek melalui operasi kelonggaran (relaksasi) sehingga penyelesaian optimum dicapai. Kerumitan masanya ialah O(V * E), dengan V ialah bilangan bucu dalam graf dan E ialah bilangan tepi.

Berikut ialah contoh kod untuk melaksanakan algoritma Bellman-Ford menggunakan C++:

#include <iostream>
#include <vector>

struct Edge {
    int source;
    int destination;
    int weight;
};

void BellmanFord(std::vector<Edge>& edges, int numVertices, int source) {
    std::vector<int> distance(numVertices, INT_MAX);
    distance[source] = 0;

    // Relaxation
    for (int i = 1; i < numVertices; i++) {
        for (const auto& edge : edges) {
            int u = edge.source;
            int v = edge.destination;
            int w = edge.weight;
            if (distance[u] != INT_MAX && distance[v] > distance[u] + w) {
                distance[v] = distance[u] + w;
            }
        }
    }

    // Check for negative cycle
    for (const auto& edge : edges) {
        int u = edge.source;
        int v = edge.destination;
        int w = edge.weight;
        if (distance[u] != INT_MAX && distance[v] > distance[u] + w) {
            std::cout << "图中存在负权回路
";
            return;
        }
    }

    // 输出最短路径
    for (int i = 0; i < numVertices; i++) {
        if (distance[i] == INT_MAX) {
            std::cout << "源点无法到达顶点 " << i << "
";
        } else {
            std::cout << "源点到顶点 " << i << " 的最短路径为: " << distance[i] << "
";
        }
    }
}

int main() {
    std::vector<Edge> graph = { 
        {0, 1, -1},
        {0, 2, 4},
        {1, 2, 3},
        {1, 3, 2},
        {1, 4, 2},
        {3, 2, 5},
        {3, 1, 1},
        {4, 3, -3}
    };
    int numVertices = 5;
    int source = 0;

    BellmanFord(graph, numVertices, source);

    return 0;
}

Dalam kod di atas, kami mentakrifkan struktur tepi (Tepi), termasuk titik permulaan (sumber), titik penamat (destinasi) dan berat (berat).

Fungsi BellmanFord menerima senarai tepi, bilangan bucu dalam graf dan titik sumber sebagai argumen. Ia mula-mula memulakan jarak tatasusunan jarak, menetapkan jarak titik sumber kepada 0, dan menetapkan jarak bucu lain kepada infiniti.

Kemudian lakukan operasi relaksasi pusingan V-1, melintasi set tepi setiap kali dan cuba mengemas kini laluan terpendek. Jika laluan yang lebih pendek boleh diperolehi dengan melonggarkan tepi, jarak ke bucu sasaran dikemas kini. Dengan cara ini, laluan terpendek dari titik sumber ke bucu lain boleh ditemui.

Akhir sekali, kami melintasi semua tepi sekali lagi dan memeriksa sama ada terdapat kitaran berat negatif. Jika tepi masih boleh mengemas kini jarak bucu sasaran selepas operasi kelonggaran, ini bermakna terdapat gelung berat negatif dalam graf.

Output akhir kod ialah laluan terpendek. Jika jarak ke puncak masih tidak terhingga, ini bermakna titik sumber tidak boleh mencapai puncak jika tidak, laluan terpendek dari titik sumber ke puncak adalah output.

Di atas ialah contoh kod menggunakan C++ untuk melaksanakan algoritma Bellman-Ford. Anda boleh mengubah suai dan memanjangkannya mengikut keperluan anda. Algoritma ini sangat berguna apabila berurusan dengan graf dengan tepi berat negatif Saya harap ia akan membantu anda.

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