Discussion :

[jesse100]

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

[koala01]

Salut,

Oui ... et la question est ... ????

Il faut savoir que, si nous ne refusons jamais de donner un coup de main, nous ne ferons jamais tes exercices pour toi, car ce serait le pire des services à te rendre...

Donc, si tu as un problème avec l'algorithme de Dijkstra, dis nous ce qui te chagrine avec, explique nous les problèmes que tu rencontre et nous pourrons -- peut-être -- t'aider...