Introduction
Je suis toujours sur Codingame et pour l'un des challenges je cherchais un exemple simple d'implémentation de l'algorithme de Dijkstra en C++ sur lequel je pourrais expérimenter etc. Je n'ai pas trouvé ce que je cherchais car soit le code C++ n'utilisait pas la STL, soit le code était très long, soit il n'utilisait pas de priority_queue soit encore le code n'était pas prêt à l'emploi.
Show me the code
Bref, voilà le source avec lequel j'ai fait mes propres tests. Le code est complet, relativement court (moins de 80 lignes avec pas mal de commentaires) et autonome (on peut faire un copier-coller et ça tourne). Pour les fichiers de test (voir un peu plus en bas dans cette page) il faudra juste penser à utiliser le bon nom de fichier à la ligne 13.
|
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
#include <iostream>#include <queue>#include <vector>#include <fstream>#include <limits>using namespace std;auto comp = [](const pair<int, int> &a, const pair<int, int> &b) {return a.second > b.second; };int main() { ifstream TestFile("Test Dijkstra 3.txt", ios::in); // open the test file if (!TestFile) return 1; cin.rdbuf(TestFile.rdbuf()); int NbNodes, NbEdges; cin >> NbNodes >> NbEdges; vector<vector<pair<int, int>>> G(NbNodes); // The graph is a vector with NbNodes nodes. // Each node is connected to others nodes via weighted edges. This information is stored in a vector of pair for (auto i = 0; i != NbEdges; ++i) { int u, v, w; cin >> u >> v >> w; G[u].push_back(make_pair(v, w)); // Each pair contains : first=index of the node connected to u, second=weight/distance/codst of the path from v to u //G[v].push_back(make_pair(u, w)); // Comment this line if the graph use directed edges. // With undirected edges, create link from v to u and u to v. Both with weight w } int StartNode; cin >> StartNode; vector<int> Distances(NbNodes, numeric_limits<int>::max()); // Distances is a vector of NbNodes cells. All cells are initialized with max() // Distances[i] is the distance from StartNode to node whose index is i Distances[StartNode] = 0; // Distance to StartNode is initialized to 0 vector<int> Parents(NbNodes, -1); // Parents is a vector of NbNodes cells. All cells are initialized with -1 // Priority queue storing pairs and using a specific comparator function // Because of the comparator we need to specify the 3 parameters // The comparator make sure that the closest node is always on top of the queue // Each pair is made of : index of the node and the distance to StartNode priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> Q(comp); Q.push(make_pair(StartNode, 0)); // Initialize the priority queue with StartNode while (!Q.empty()) { // Dijkstra int v = Q.top().first; // get the index of the nearest node int w = Q.top().second; // get the weight/cost/distance Q.pop(); if (w <= Distances[v]) { // Pay attention to this test. // It can be removed, however, it avoid duplicated work for (const auto& i : G[v]) { // v is the index of the nearest node auto v2 = i.first; // For each node connected to node v auto w2 = i.second; if (Distances[v] + w2 < Distances[v2]) { // If distance from StartNode to v2 thru v is shorter then the current distance from StartNode to v2 Distances[v2] = Distances[v] + w2; // then update the distance from StartNode to v2 and parent[v2] Q.push(make_pair(v2, Distances[v2])); } } } } for (auto i = 0; i != NbNodes; ++i) { // display the results cout << "\nPath from node " << StartNode << " to node " << i << " cost " << Distances[i] << endl; cout << i; for (auto p = Parents[i]; p != -1; p = Parents[p]) cout << " <- " << p; // when links are not bi directional the output is accurate when using <- instead of -> cout << endl; // otherwise it make no difference } getchar();} |
Fichiers d'exemple à utiliser
Le format est très simple :
- Sur la première ligne on a le nombre de nœuds (de 0 à n-1) et le nombre de liens.
- Ensuite sur chaque ligne on a nœud 1, nœud 2 puis le poids de la liaison en question.
- Sur la dernière ligne on précise le nœud pour lequel on cherche le nœud le plus proche.
Il ne faut pas oublier que chaque liaison est bidirectionnelle. Voir plus bas les commentaires dans le code.
A noter dans l'exemple ci-dessous qu'il y a deux liaisons entre les nœuds 3 et 4 dont les poids respectifs sont 1 et 8.
6 10 0 1 9 0 3 2 1 2 11 1 4 3 2 4 5 2 5 12 3 1 4 3 4 8 4 3 1 4 5 6 0
Autre exemple de fichier :
6 6 0 1 3 0 3 7 1 2 10 1 3 3 3 4 1 3 5 2 1
Dernier fichier correspondant à la vidéo YouTube qui est dans les commentaires. Attention, pour l'utiliser il faut commenter la ligne 26 du code source car comme on le voit dans la vidéo, les liaisons entre nœuds sont directionnelles :
8 140 1 200 3 800 6 901 5 102 3 102 5 502 7 203 2 103 6 204 1 504 6 305 2 105 3 406 0 200
Explications
Exemple de sortie console quand on utilise le troisième fichier.
Pour chaque nœud, on retrouve le poids total du chemin qui va de la source au nœud en question. Par exemple, pour le nœud 4 il n'y a pas de chemin. Le poids est donc infini (2147483647) et on observe qu'il n'y a pas de chemin affiché. Pour le nœud 5, le coût total est de 30. Cela se décompose en un brin qui va de 0 à 1 et qui coûte 20 puis un autre qui va de 1 à 5 et qui coûte 10.
ATTENTION : comme indiqué dans le code source, pour obtenir une sortie exacte avec le fichier test3 il faut commenter la ligne 26. En effet, le troisième graphe est directionnel. Autrement dit on peut avoir une liaison de 2 vers 3 mais pas de liaison de 3 vers 2 par exemple. Quand le graphe est bidirectionnel il ne faut pas commenter la ligne 26. Bien sûr, dans ce cas, au niveau de la sortie écran, les "flèches" indiquent toujours le chemin de la source vers le nœud considéré mais le parcours peut tout aussi bien se faire du nœud vers la source et/ou de la source vers le nœud.
Leave a Reply