Dijkstra's Algorithm - Shortest Path

Feroz Ahmad bio photo By Feroz Ahmad Comment
Concept of Set can be understood by following code :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include<set>
using namespace std;
int main() {
// your code goes here
set <pair<int,int>> S;
set <pair<int,int>> :: iterator it;
S.insert({2,100});
S.insert({1,200});
S.insert({1,50});
for(it = S.begin();it!=S.end();it++)
{
cout<<(*it).first<<" "<<(*it).second<<endl;
}
return 0;
}
Output: 1 50 1 200 2 100 This property of set can be easily utilized, that set keeps all its elements in kind of sorted order. (using Red-Black Trees) Psuedocode  from CLRS :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function Dijkstra(Graph, source):
     create vertex set Q
     for each vertex v in Graph:             // Initialization
         dist[v]  INFINITY                  // Unknown distance from source to v
         prev[v]  UNDEFINED                 // Previous node in optimal path from source
         add v to Q                          // All nodes initially in Q (unvisited nodes)
     dist[source]  0                        // Distance from source to source
     while Q is not empty:
         u  vertex in Q with min dist[u]    // Source node will be selected first
         remove u from Q 
         for each neighbor v of u:           // where v is still in Q.
             alt  dist[u] + length(u, v)
             if alt < dist[v]:               // A shorter path to v has been found
                 dist[v]  alt
                 prev[v]  u
     return dist[], prev[]
Check out the code for SPOJ - SHPATH at : http://ideone.com/Ip8Kzf
comments powered by Disqus