Étant donné un graphe non orienté pondéré, trouvez le chemin le plus court entre deux sommets donnés en utilisant l'algorithme de Dijkstra.


Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
 
#define MAXN 100005
#define MAXM 200005
#define INF 0x3f3f3f3f
 
int n, m;
int u[MAXM], v[MAXM], w[MAXM], head[MAXN], cnt;
int dist[MAXN];
bool vis[MAXN];
 
inline void add_edge(int x, int y, int z) {
    u[++cnt] = x, v[cnt] = y, w[cnt] = z;
    head[x] = cnt;
}
 
inline void dijkstra(int s, int t) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
    heap.push({0, s});
    dist[s] = 0;
 
    while (!heap.empty()) {
        int x = heap.top().second;
        heap.pop();
        if (vis[x])
            continue;
        vis[x] = true;
        for (int i = head[x]; i; i = head[x]) {
            int y = v[i];
            if (dist[y] > dist[x] + w[i]) {
                dist[y] = dist[x] + w[i];
                heap.push({dist[y], y});
            }
        }
    }
    printf("The shortest distance from vertex %d to vertex %d is: %d\n", s, t, dist[t]);
}
 
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        add_edge(x, y, z);
    }
    memset(dist, 0x3f, sizeof(dist));
    int s, t;
    cin >> s >> t;
    dijkstra(s, t);
    return 0;
}