fork download
copy 
  1. #include <climits>
  2. #include <iostream>
  3. #include <set>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. // spravíme si struct na uloženie hrany:
  8. // "to" je kam vedie, "length" je jej dĺžka
  9.  
  10. struct edge { int to, length; };
  11.  
  12. // funkcia dijkstra() vráti dĺžku najkratšej cesty v grafe "graph"
  13. // z vrcholu "source" do vrcholu "target"
  14.  
  15. // v "graph" musia mať všetky hrany nezáporné dĺžky
  16.  
  17. // všimnite si odovzdanie parametru "graph" const-referenciou, aby sa 
  18. //     zbytočne nekopíroval
  19.  
  20. int dijkstra(const vector< vector<edge> > &graph, int source, int target) {
  21.  
  22. 	// inicializácia: vzdialenosť "source" je 0, ostatné vrcholy nekonečno
  23.     vector<int> min_distance( graph.size(), INT_MAX );
  24.     min_distance[ source ] = 0;
  25.  
  26.     // active_vertices je množina obsahujúca záznamy tvaru "(d,v)"
  27.     //     kde "v" je ešte nespracovaný vrchol 
  28.     //     a "d" je doteraz najlepšia známa vzdialenosť zo "source" do "v"
  29.  
  30.     // keďže set<> v C++ je usporiadaný, je táto množina usporiadaná primárne
  31.     //     podľa vzdialenosti od "source"
  32.  
  33.     set< pair<int,int> > active_vertices;
  34.     active_vertices.insert( {0,source} );
  35.  
  36.     // dokola opakujeme:
  37.     //     vyber nespracovaný vrchol najbližší ku "source"
  38.     //     tento vrchol je odteraz definitívne spracovaný
  39.     //     prejdi všetky hrany z neho a skús zmenšiť vzdialenosti do susedov
  40.  
  41.     while (!active_vertices.empty()) {
  42.  
  43.     	// zisti, ktorý vrchol ideme spracúvať
  44. 	    int where = active_vertices.begin()->second;
  45.  
  46. 	    // ak je to "target", sme hotoví
  47.     	if (where == target) return min_distance[where];
  48.  
  49.     	// zmaž jeho záznam spomedzi vrcholov čakajúcich na spracovanie
  50.     	active_vertices.erase( active_vertices.begin() );
  51.  
  52.     	// prejdi všetky hrany vychádzajúce z "where"
  53.     	for (const auto &ed : graph[where])
  54.     	    // pozri, či touto hranou niečo zlepšíme
  55.     		if (min_distance[ed.to] > min_distance[where] + ed.length) {
  56.     			// ak vieme zlepšiť vzdialenosť do "ed.to", zmažeme starý
  57.     			//     záznam o tomto vrchole ...
  58.     			//     (ak mal doteraz min_distance == INT_MAX a teda ešte nemal
  59.     			//     záznam v active_vertices, nič sa nezmaže)
  60.     			active_vertices.erase( { min_distance[ed.to], ed.to } );
  61.     			// ... zlepšíme mu zapamätanú vzdialenosť ... 
  62.     			min_distance[ed.to] = min_distance[where] + ed.length;
  63.     			// ... a vyrobíme o ňom nový záznam
  64.     			active_vertices.insert( { min_distance[ed.to], ed.to } );
  65.     		}
  66.     	}
  67.  
  68.     // ak sme sa dostali až sem, cesta zo "source" do "target" neexistuje
  69.     return INT_MAX;
  70. }
  71.  
  72. int main() {
  73. 	// test na miniatúrnom grafe:
  74. 	// (0) ---1--> (1) ---1---> (2) ---1--> (3)
  75. 	//  \                                  /
  76. 	//   -----------------2--------------->
  77.  
  78. 	vector< vector<edge> > graph = { { {1,1}, {3,2} }, { {2,1} }, { {3,1} }, { } };
  79. 	cout << dijkstra(graph,0,3) << endl; // vypíše 2
  80. 	cout << dijkstra(graph,0,2) << endl; // vypíše 2
  81. 	cout << dijkstra(graph,1,2) << endl; // vypíše 1
  82. 	cout << dijkstra(graph,2,0) << endl; // vypíše INT_MAX
  83. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
2
1
2147483647
https://ideone.com/MLvpXv
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!