Cara menggunakan algoritma Dijkstra dalam C++

Bagaimana untuk menggunakan algoritma Dijkstra dalam C++?

Algoritma Dijkstra ialah algoritma tamak yang digunakan untuk mencari laluan terpendek antara dua bucu dalam graf berwajaran. Idea terasnya adalah untuk mengembangkan laluan terpendek secara beransur-ansur dengan mengemas kini jarak terpendek secara berterusan dari bucu permulaan ke bucu lain.

Yang berikut akan memperkenalkan cara menggunakan C++ untuk melaksanakan algoritma Dijkstra dan memberikan contoh kod khusus.

Melaksanakan algoritma Dijkstra memerlukan langkah berikut:

Langkah 1: Permulaan.

Pertama, kita perlu memulakan beberapa struktur data, termasuk permulaan bucu permulaan, jarak tatasusunan jarak terpendek dan tatasusunan status lawatan yang dilawati. Permulaan bucu permulaan menentukan titik permulaan laluan terpendek, jarak tatasusunan jarak terpendek digunakan untuk merekod jarak terpendek semasa dari bucu permulaan ke bucu lain, dan tatasusunan status akses yang dilawati digunakan untuk menandakan sama ada bucu telah dilawati .

Langkah 2: Mulakan tatasusunan jarak terpendek.

Mulakan jarak terpendek dari bucu permulaan ke bucu lain hingga tak terhingga, dan mulakan jarak terpendek dari bucu permulaan ke bucu sendiri kepada 0. Juga menandakan puncak permulaan sebagai dilawati.

Langkah 3: Kemas kini tatasusunan jarak terpendek.

Untuk semua bucu bersebelahan dengan bucu permulaan, jika laluan yang lebih pendek boleh ditemui melalui bucu permulaan, kemas kini tatasusunan jarak terpendek. Kaedah kemas kini khusus adalah untuk menambah jarak dari bucu permulaan ke bucu semasa ditambah berat tepi dari bucu permulaan ke bucu semasa, dan membandingkannya dengan jarak terpendek asal dari bucu semasa.

Langkah 4: Pilih bucu terdekat seterusnya.

Pilih bucu yang paling hampir dengan bucu permulaan daripada bucu yang belum dilawati sebagai bucu seterusnya yang akan dilawati.

Langkah 5: Ulang langkah 3 dan 4.

Ulang langkah 3 dan 4 sehingga semua bucu telah dilawati. Akhir sekali, apa yang disimpan dalam dist tatasusunan jarak terpendek ialah jarak terpendek dari bucu permulaan ke setiap bucu.

Berikut ialah contoh kod yang menggunakan C++ untuk melaksanakan algoritma Dijkstra:

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

vector<int> dijkstra(vector<vector<int>>& graph, int start) {
    int numVertices = graph.size();

    vector<int> dist(numVertices, INT_MAX); // 最短距离数组
    vector<bool> visited(numVertices, false); // 访问状态数组

    dist[start] = 0;

    for (int i = 0; i < numVertices - 1; i++) {
        int minDist = INT_MAX;
        int minIndex = -1;
        
        // 选取下一个最近顶点
        for (int j = 0; j < numVertices; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                minIndex = j;
            }
        }

        visited[minIndex] = true;

        // 更新最短距离数组
        for (int j = 0; j < numVertices; j++) {
            if (!visited[j] && graph[minIndex][j] && dist[minIndex] != INT_MAX && dist[minIndex] + graph[minIndex][j] < dist[j]) {
                dist[j] = dist[minIndex] + graph[minIndex][j];
            }
        }
    }

    return dist;
}

int main() {
    vector<vector<int>> graph = {
        {0, 2, 4, 0, 0},
        {2, 0, 1, 3, 0},
        {4, 1, 0, 0, 2},
        {0, 3, 0, 0, 3},
        {0, 0, 2, 3, 0}
    };

    vector<int> shortestDist = dijkstra(graph, 0);

    cout << "起始顶点到各个顶点的最短距离：" << endl;
    for (int i = 0; i < shortestDist.size(); i++) {
        cout << "到顶点 " << i << " 的最短距离为：" << shortestDist[i] << endl;
    }

    return 0;
}

Dalam kod di atas, kami mewakili graf berwajaran melalui matriks dua dimensi Setiap elemen dalam matriks mewakili jarak antara dua bucu berat badan. Akhir sekali, jarak terpendek dari bucu permulaan ke setiap bucu ialah keluaran.

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