fork(107) download
copy 
  1. //Implementation for Dijkstra's SSSP(Single source shortest path) algorithm
  2. //This is an optimized algorithm running in O(E*log(V))
  3.  
  4. #include <iostream>
  5. #include <queue>
  6. #include <vector>
  7. #include <climits>
  8. using namespace std;
  9. #define INF INT_MAX //Infinity
  10.  
  11. const int sz=10001; //Maximum possible number of vertices. Preallocating space for DataStructures accordingly
  12. vector<pair<int,int> > a[sz]; //Adjacency list
  13. int dis[sz]; //Stores shortest distance
  14. bool vis[sz]={0}; //Determines whether the node has been visited or not
  15.  
  16. void Dijkstra(int source, int n) //Algorithm for SSSP
  17. {
  18.     for(int i=0;i<sz;i++) //Set initial distances to Infinity
  19.         dis[i]=INF;
  20.     //Custom Comparator for Determining priority for priority queue (shortest edge comes first)
  21.     class prioritize{public: bool operator ()(pair<int, int>&p1 ,pair<int, int>&p2){return p1.second>p2.second;}};
  22.     priority_queue<pair<int,int> ,vector<pair<int,int> >, prioritize> pq; //Priority queue to store vertex,weight pairs
  23.     pq.push(make_pair(source,dis[source]=0)); //Pushing the source with distance from itself as 0
  24.     while(!pq.empty())
  25.     {
  26.         pair<int, int> curr=pq.top(); //Current vertex. The shortest distance for this has been found
  27.         pq.pop();
  28.         int cv=curr.first,cw=curr.second; //'cw' the final shortest distance for this vertex
  29.         if(vis[cv]) //If the vertex is already visited, no point in exploring adjacent vertices
  30.             continue;
  31.         vis[cv]=true;
  32.         for(int i=0;i<a[cv].size();i++) //Iterating through all adjacent vertices
  33.             if(!vis[a[cv][i].first] && a[cv][i].second+cw<dis[a[cv][i].first]) //If this node is not visited and the current parent node distance+distance from there to this node is shorted than the initial distace set to this node, update it
  34.                 pq.push(make_pair(a[cv][i].first,(dis[a[cv][i].first]=a[cv][i].second+cw))); //Set the new distance and add to priority queue
  35.     }
  36. }
  37.  
  38. int main() //Driver Function for Dijkstra SSSP
  39. {
  40.     int n,m,x,y,w;//Number of vertices and edges
  41.     //cout<<"Enter number of vertices and edges in the graph\n";
  42.     cin>>n>>m;
  43.     for(int i=0;i<m;i++) //Building Graph
  44.     {
  45.         cin>>x>>y>>w; //Vertex1, Vertex2, weight of edge
  46.         a[x].push_back(make_pair(y,w));
  47.         a[y].push_back(make_pair(x,w));
  48.     }
  49.     //cout<<"Enter source for Dijkstra's SSSP algorithm\n";
  50.     int source;
  51.     cin>>source;
  52.     Dijkstra(source,n);//SSSP from source (Also passing number of vertices as parameter)
  53.     cout<<"Source is: "<<source<<". The shortest distance to every other vertex from here is: \n";
  54.     for(int i=1;i<=n;i++)//Printing final shortest distances from source
  55.     {
  56.         cout<<"Vertex: "<<i<<" , Distance: ";
  57.         dis[i]!=INF? cout<<dis[i]<<"\n" : cout<<"-1\n";
  58.     }
  59.     return 0;
  60. }
Success #stdin #stdout 0s 3628KB
comments (?)
stdin
copy 
5 5
1 2 3
2 5 5
1 5 4
1 3 2
3 4 3
1
stdout
copy 
Source is: 1. The shortest distance to every other vertex from here is: 
Vertex: 1 , Distance: 0
Vertex: 2 , Distance: 3
Vertex: 3 , Distance: 2
Vertex: 4 , Distance: 5
Vertex: 5 , Distance: 4
https://ideone.com/qkmt31
language:
C++14 (gcc 8.3)
created:
9 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!