fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <limits>
  4. #include <queue>
  5.  
  6. const int INF = std::numeric_limits<int>::max();
  7.  
  8. // Fungsi untuk implementasi algoritma Dijkstra
  9. void dijkstra(const std::vector<std::vector<int>>& graph, int startNode) {
  10.     int numNodes = graph.size();
  11.     std::cout << numNodes << "\n";
  12.  
  13.     // Inisialisasi vektor jarak dengan infinity, kecuali startNode
  14.     std::vector<int> distance(numNodes, INF);
  15.     distance[startNode] = 0;
  16.  
  17.     // Priority Queue untuk menyimpan pasangan (jarak, simpul)
  18.     std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
  19.     pq.push({0, startNode});
  20.  
  21.     while (!pq.empty()) {
  22.         int u = pq.top().second;
  23.         std::cout << u << "\n";
  24.         pq.pop();
  25.  
  26.         for (int v = 0; v < numNodes; ++v) {
  27.             if (graph[u][v] != INF) {
  28.                 int newDistance = distance[u] + graph[u][v];
  29.  
  30.                 if (newDistance < distance[v]) {
  31.                     distance[v] = newDistance;
  32.                     pq.push({distance[v], v});
  33.                 }
  34.             }
  35.         }
  36.     }
  37.  
  38.     // Menampilkan jarak terpendek dari startNode ke semua simpul
  39.     std::cout << "Shortest distances from node " << startNode << ":\n";
  40.     for (int i = 0; i < numNodes; ++i) {
  41.         std::cout << "To node " << i << ": ";
  42.         if (distance[i] == INF) {
  43.             std::cout << "Infinity\n";
  44.         } else {
  45.             std::cout << distance[i] << "\n";
  46.         }
  47.     }
  48. }
  49.  
  50. /*
  51. node 0: JICA
  52. node 1: Kolam Renang
  53. node 2: Gymnasium
  54. node 3: FPOK B
  55. node 4: FPOK A
  56. node 5: Kantin FIP & FK
  57. node 6: FPMIPA B & C
  58. node 7: FIP
  59. node 8: Perpustakaan
  60. node 9: STI
  61. node 10: SMA UPI & Poliklinik
  62. node 11: Sekolah Pascasarjana & Direktorat
  63. node 12: Gedung Ahmad Sanusi & Parkiran
  64. node 13: FPTK 2
  65. node 14: Gerbang Masuk Gerlong
  66. node 15: FPTK 1
  67. node 16: Masjid Al-Furqon
  68. node 17: Gerbang Utama
  69. node 18: Amphitheatre
  70. node 19: FPSD
  71. node 20: FPIPS
  72. node 21: UC
  73. node 22: FPEB & Balai Bahasa
  74. node 23: Asrama
  75. node 24: Lapangan Tenis
  76. node 25: Museum, Parkiran Atas, dan ATM
  77. node 26: FPBS
  78. node 27: Isola
  79. node 28: Taman
  80. */
  81.  
  82. int main() {
  83.     // Matriks ketetanggaan
  84.     std::vector<std::vector<int>> graph = {
  85.         {0, 465, 389, 270, 198, 170, 100, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
  86.         {465, 0, 300, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
  87.         {389, 300, 0, 119, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 208, INF, INF, INF, INF, INF},
  88.         {270, INF, 119, 0, 15, INF, INF, INF, 196, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 162, INF, INF, INF, INF},
  89.         {198, INF, INF, 15, 0, 78, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
  90.         {170, INF, INF, INF, 78, 0, 147, INF, 184, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
  91.         {100, INF, INF, INF, INF, 147, 0, 94, 179, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
  92.         {INF, INF, INF, INF, INF, INF, 94, 0, 117, 105, 162, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
  93.         {INF, INF, INF, 196, INF, 184, 179, 117, 0, 96, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 97, INF, INF, INF, INF},
  94.         {INF, INF, INF, INF, INF, INF, INF, 105, 96, 0, 240, INF, INF, INF, INF, INF, INF, INF, INF, INF, 151, 197, INF, INF, INF, INF, INF, INF, INF},
  95.         {INF, INF, INF, INF, INF, INF, INF, 162, INF, 240, 0, 101, INF, INF, INF, INF, INF, INF, INF, 174, 140, INF, INF, INF, INF, INF, INF, INF, INF},
  96.         {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 101, 0, 80, INF, INF, INF, 143, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
  97.         {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 80, 0, 85, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
  98.         {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 85, 0, 70, INF, 136, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
  99.         {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 70, 0, 141, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
  100.         {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 141, 0, 90, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
  101.         {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 143, INF, 136, INF, 90, 0, 168, 174, 200, INF, INF, INF, INF, INF, INF, INF, INF, INF},
  102.         {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 168, 0, 221, INF, INF, INF, INF, INF, INF, INF, 320, 285, INF},
  103.         {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 174, 221, 0, 114, INF, INF, INF, INF, INF, INF, 221, 160, INF},
  104.         {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 174, INF, INF, INF, INF, INF, 200, INF, 114, 0, 196, INF, INF, INF, INF, INF, 142, INF, INF},
  105.         {INF, INF, INF, INF, INF, INF, INF, INF, INF, 151, 140, INF, INF, INF, INF, INF, INF, INF, INF, 196, 0, 46, INF, INF, INF, INF, 66, INF, INF},
  106.         {INF, INF, INF, INF, INF, INF, INF, INF, INF, 197, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 46, 0, 80, INF, INF, 210, INF, INF, INF},
  107.         {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 80, 0, 191, 190, 210, INF, INF, INF},
  108.         {INF, INF, 208, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 191, 0, 50, INF, INF, INF, INF},
  109.         {INF, INF, INF, 162, INF, INF, INF, INF, 97, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 190, 50, 0, INF, INF, INF, INF},
  110.         {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 210, 210, INF, INF, 0, 127, INF, 85},
  111.         {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 320, 221, 142, 66, INF, INF, INF, INF, 127, 0, 65, 85},
  112.         {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 285, 160, INF, INF, INF, INF, INF, INF, INF, 65, 0, 20},
  113.         {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 85, 85, 20, 0}
  114.     };
  115.  
  116.     // Panggil fungsi Dijkstra dengan simpul awal 0
  117.     dijkstra(graph, 0);
  118.  
  119.     return 0;
  120. }
  121.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
29
0
6
5
7
4
3
3
8
9
2
10
24
2
23
20
11
1
21
26
19
12
23
22
27
16
28
13
25
18
15
14
25
18
17
17
Shortest distances from node 0:
To node 0: 0
To node 1: 465
To node 2: 332
To node 3: 213
To node 4: 198
To node 5: 170
To node 6: 100
To node 7: 194
To node 8: 279
To node 9: 299
To node 10: 356
To node 11: 457
To node 12: 537
To node 13: 622
To node 14: 692
To node 15: 690
To node 16: 600
To node 17: 768
To node 18: 644
To node 19: 530
To node 20: 450
To node 21: 496
To node 22: 565
To node 23: 425
To node 24: 375
To node 25: 643
To node 26: 516
To node 27: 581
To node 28: 601
https://ideone.com/wMjv8W
language:
C++14 (gcc 8.3)
created:
2 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!