fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <climits>
  5.  
  6. using namespace std;
  7.  
  8. void dijkstra(int start, vector<vector<pair<int, int>>> &graph) {
  9.     int n = graph.size();
  10.     vector<int> distance(n, INT_MAX); // Najkrótsze odległości
  11.     distance[start] = 0;
  12.  
  13.     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // Min-kolejka
  14.     pq.push({0, start});
  15.  
  16.     while (!pq.empty()) {
  17.         int dist = pq.top().first;
  18.         int node = pq.top().second;
  19.         pq.pop();
  20.  
  21.         if (dist > distance[node]) continue;
  22.  
  23.         for (auto &neighbor : graph[node]) {
  24.             int nextNode = neighbor.first;
  25.             int weight = neighbor.second;
  26.  
  27.             if (distance[node] + weight < distance[nextNode]) {
  28.                 distance[nextNode] = distance[node] + weight;
  29.                 pq.push({distance[nextNode], nextNode});
  30.             }
  31.         }
  32.     }
  33.  
  34.     // Wyświetlanie wyników
  35.     for (int i = 0; i < n; i++) {
  36.         if (distance[i] == INT_MAX)
  37.             cout << "Wierzchołek " << i << ": brak ścieżki" << endl;
  38.         else
  39.             cout << "Wierzchołek " << i << ": " << distance[i] << endl;
  40.     }
  41. }
  42.  
  43. int main() {
  44.     int n = 6; // Liczba wierzchołków
  45.     vector<vector<pair<int, int>>> graph(n);
  46.  
  47.     // Dodawanie krawędzi (wierzchołek, waga)
  48.     graph[0].push_back({1, 4});
  49.     graph[0].push_back({2, 1});
  50.     graph[2].push_back({1, 2});
  51.     graph[1].push_back({3, 1});
  52.     graph[2].push_back({3, 5});
  53.     graph[3].push_back({4, 3});
  54.     graph[4].push_back({5, 2});
  55.  
  56.     int start = 0; // Wierzchołek startowy
  57.     dijkstra(start, graph);
  58.  
  59.     return 0;
  60. }
  61.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Wierzchołek 0: 0
Wierzchołek 1: 3
Wierzchołek 2: 1
Wierzchołek 3: 4
Wierzchołek 4: 7
Wierzchołek 5: 9
https://ideone.com/4q4A9X
language:
C++ (gcc 8.3)
created:
4 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!