fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. pair<int, vector<string>> dijikstra(unordered_map<string, vector<pair<string, int>>> graph,  string src,  string dest) {
  6.     // Priority queue to hold nodes to be explored with the current shortest time to reach them
  7.     priority_queue<pair<int, vector<string>>, vector<pair<int, vector<string>>>, greater<>> pq; // Min heap to sort in asc order
  8.     pq.push({0, {src}});
  9.  
  10.     unordered_map<string, int> best_time;
  11.     best_time[src] = 0;
  12.  
  13.     while (!pq.empty()) {
  14.         pair<int, vector<string>> current = pq.top();
  15.         pq.pop();
  16.         int current_time = current.first; 
  17.         vector<string> path = current.second;
  18.         string current_node = path.back();
  19.  
  20.         // If we reach the destination, return the time and path
  21.         if (current_node == dest) {
  22.             return {current_time, path};
  23.         }
  24.  
  25.         // If we have already found a better path, continue
  26.         if (current_time > best_time[current_node]) {
  27.             continue;
  28.         }
  29.  
  30.         // Explore neighbors
  31.         for (int i = 0; i < graph[current_node].size(); i++) {
  32.  
  33.             pair<string, int> neighbor = graph[current_node][i];
  34.             int new_time = current_time + neighbor.second;
  35.  
  36.             if (best_time.find(neighbor.first) == best_time.end() || new_time < best_time[neighbor.first]) {
  37.                 best_time[neighbor.first] = new_time;
  38.  
  39.                 vector<string> new_path = path;
  40.                 new_path.push_back(neighbor.first);
  41.                 pq.push({new_time, new_path});
  42.             }
  43.         }
  44.     }
  45.  
  46.     // If no path is found
  47.     return {-1, {}};
  48. }
  49.  
  50. int main() {
  51.     // adjacency list
  52.     unordered_map<string, vector<pair<string, int>>> graph ;
  53.     graph["A"].push_back(make_pair("B", 1));
  54.     graph["A"].push_back(make_pair("C", 8));
  55.  
  56.     graph["B"].push_back(make_pair("C", 6));
  57.     graph["B"].push_back(make_pair("D", 5));
  58.  
  59.     graph["C"].push_back(make_pair("D", 1));
  60.     graph["C"].push_back(make_pair("E", 2));
  61.  
  62.     graph["D"].push_back(make_pair("E", 4));
  63.  
  64.  
  65.     /*      Other way to initialise
  66.          unordered_map<string, vector<pair<string, int>>> graph = {
  67.                 {"A", {{"B", 1}, {"C", 8}}},
  68.                 {"B",  {{"C", 6}, {"D", 5}}},
  69.                 {"C", {{"D", 1}, {"E", 2}}},
  70.                 {"D", {{"E", 4}}}
  71.         };
  72.  
  73.     */
  74.  
  75.     string source = "A";
  76.     string destination = "E";
  77.     pair<int, vector<string>> result = dijikstra(graph, source, destination);
  78.  
  79.  
  80.     cout << "Shortest time is " << result.first <<endl;
  81.     for (int i = 0; i < result.second.size(); i++) {
  82.         cout << result.second[i] << " ";
  83.     }
  84.     cout << endl;
  85.  
  86.     return 0;
  87. }
  88.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Shortest time is 9
A B C E
https://ideone.com/1QEs4V
language:
C++ (gcc 8.3)
created:
5 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!