fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <limits>
  5. #include <iomanip>
  6.  
  7. using namespace std;
  8.  
  9. // Definicja typu dla pary (waga, wierzchołek)
  10. // Używamy 'long long' dla odległości, aby uniknąć przepełnienia w dużych grafach
  11. const long long INF = numeric_limits<long long>::max();
  12. typedef pair<long long, int> pii;
  13.  
  14. // Funkcja implementująca algorytm Dijkstry
  15. vector<long long> dijkstra(int V, const vector<vector<pair<int, int>>>& adj, int start_node) {
  16.     // 1. Inicjalizacja:
  17.     // wektor odległości, początkowo nieskończoność dla wszystkich wierzchołków
  18.     vector<long long> dist(V, INF); 
  19.  
  20.     // kolejka priorytetowa przechowująca pary (odległość, wierzchołek)
  21.     // używamy greater, aby zaimplementować min-heap (kolejka priorytetowa dla minimalnych wartości)
  22.     priority_queue<pii, vector<pii>, greater<pii>> pq;
  23.  
  24.     // Ustawienie odległości źródłowego wierzchołka na 0 i dodanie go do kolejki
  25.     dist[start_node] = 0;
  26.     pq.push({0, start_node});
  27.  
  28.     // 2. Główna pętla algorytmu:
  29.     while (!pq.empty()) {
  30.         long long current_dist = pq.top().first;
  31.         int u = pq.top().second;
  32.         pq.pop();
  33.  
  34.         // Jeśli odległość wyjęta z kolejki jest większa niż już znana najkrótsza odległość, pomijamy ten wierzchołek
  35.         // (może to być stary wpis z dłuższą drogą)
  36.         if (current_dist > dist[u]) {
  37.             continue;
  38.         }
  39.  
  40.         // 3. Relaksacja krawędzi:
  41.         // Iteracja po wszystkich sąsiadach 'v' wierzchołka 'u'
  42.         for (auto& edge : adj[u]) {
  43.             int v = edge.first;
  44.             int weight = edge.second;
  45.  
  46.             // Sprawdzamy, czy nowa droga przez 'u' do 'v' jest krótsza niż dotychczas znana
  47.             if (dist[u] + weight < dist[v]) {
  48.                 // Aktualizujemy odległość do 'v'
  49.                 dist[v] = dist[u] + weight;
  50.                 // Dodajemy sąsiada do kolejki priorytetowej
  51.                 pq.push({dist[v], v});
  52.             }
  53.         }
  54.     }
  55.  
  56.     return dist;
  57. }
  58.  
  59. int main() {
  60.     // Przykład użycia:
  61.     // Graf z 6 wierzchołkami (indeksy 0 do 5)
  62.     int V = 6; 
  63.     // Lista sąsiedztwa: wektor wektorów par (sąsiad, waga krawędzi)
  64.     vector<vector<pair<int, int>>> adj(V);
  65.  
  66.     // Dodawanie krawędzi: (źródło, cel, waga)
  67.     adj[0].push_back({1, 4});
  68.     adj[0].push_back({2, 2});
  69.     adj[1].push_back({2, 5});
  70.     adj[1].push_back({3, 10});
  71.     adj[2].push_back({4, 3});
  72.     adj[3].push_back({4, 4});
  73.     adj[4].push_back({5, 5});
  74.     adj[3].push_back({5, 11});
  75.  
  76.     int start_node = 0;
  77.     // Wywołanie algorytmu Dijkstry
  78.     vector<long long> distances = dijkstra(V, adj, start_node);
  79.  
  80.     // Wyświetlanie wyników
  81.     cout << "Najkrotsze odleglosci od wierzcholka startowego " << start_node << ":\n";
  82.     for (int i = 0; i < V; ++i) {
  83.         cout << "Do wierzcholka " << i << ": ";
  84.         if (distances[i] == INF) {
  85.             cout << "Niedostepny\n";
  86.         } else {
  87.             cout << distances[i] << "\n";
  88.         }
  89.     }
  90.  
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Najkrotsze odleglosci od wierzcholka startowego 0:
Do wierzcholka 0: 0
Do wierzcholka 1: 4
Do wierzcholka 2: 2
Do wierzcholka 3: 14
Do wierzcholka 4: 5
Do wierzcholka 5: 10
https://ideone.com/gnuIQr
language:
C++ (gcc 8.3)
created:
6 days 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!