Dijkstra' s algorithm is one of the shortest path algorithms. Shortest path can be easily found using Depth First Search (DFS). But it works only for an unweighted graph. Mostly we use weighted graphs and so Dijkstra's algorithm play a vital role.
It can be implemented in many ways...
1. Adjacency matrix
2. Adjacency List (Linked list)
3. STL set container[My implementation]..
4. STL map container
I learnt this algorithm from Mark Allen Weiss book. I found many difficulties in implementing this algorithm.
This tutorial on Youtube gives a clear explanation of the implementation which made my work easier...
Source code:
Output:
It can be implemented in many ways...
1. Adjacency matrix
2. Adjacency List (Linked list)
3. STL set container[My implementation]..
4. STL map container
I learnt this algorithm from Mark Allen Weiss book. I found many difficulties in implementing this algorithm.
This tutorial on Youtube gives a clear explanation of the implementation which made my work easier...
Source code:
///for undirected graph....
#include<bits/stdc++.h>
using namespace std;
template<class T>
class Graph{
unordered_map< T, vector< pair<T,int> > >g;
unordered_map<T,int>distance;
set<pair<int,T>>dist_min_set;
vector<bool>mark;
public:
void insert_node(T u,T v,int weight){
g[u].push_back( make_pair(v,weight) );
g[v].push_back( make_pair(u,weight) );
}
void display(){
for(auto i : g){
cout << i.first <<"--> ";
for(auto it : i.second){
cout <<"("<< it.first << " , "<<it.second<<" ), ";
}
cout << "\n";
}
}
void dijkstra(T source,int n,int m){
for(auto i:g){
distance[i.first] = INT_MAX;
}
for(int i=0;i<n;i++)
mark.push_back(false);
distance[source] = 0;
dist_min_set.insert(make_pair(0,source));
while(!dist_min_set.empty()){
auto p = dist_min_set.begin();
dist_min_set.erase(dist_min_set.begin());
//mark[parent] = true;
T parent = p->second;
mark[parent] = true;
for(auto it = g[parent].begin(); it != g[parent].end(); it++){
T child = it -> first;
int weight = it ->second;
if(distance[child] > distance[parent] + weight && mark[child]==false){
//mark[child] = true;
if(distance[child] != INT_MAX){
dist_min_set.erase(dist_min_set.find(make_pair(distance[child],child)));
}
distance[child] = weight + distance[parent];
dist_min_set.insert(make_pair(distance[child],child));
}
}
}
for(auto i:g){
cout<<i.first<<" is at a distance of "<<distance[i.first]<<" from the source node\n";
}
}
};
int main(){
int n,m,weight;
cout << "Enter the number of vertices:";
cin >> n;
cout << "Enter the number of edges";
cin >> m;
Graph<string>g;
string u,v;
for(int i = 0;i < m;i++){
cout << "Enter u,v and weight";
cin >> u >> v >> weight;
g.insert_node(u,v,weight);
cout << "\n";
}
g.display();
g.dijkstra(0,n,m);
}
Output:
Enter the number of vertices:4
Enter the number of edges5
Enter u,v and weightChennai madurai 300
Enter u,v and weightChennai Trichy 150
Enter u,v and weightTrichy Salem 400
Enter u,v and weightSalem madurai 100
Enter u,v and weightTrichy madurai 50
Salem--> (Trichy , 400 ), (madurai , 100 )
Trichy--> (Chennai , 150 ), (Salem , 400 ), (madurai , 50 )
madurai--> (Chennai , 300 ), (Salem , 100 ), (Trichy , 50 )
Chennai--> (madurai , 300 ), (Trichy , 150 )
Salem is at a distance of 300 from the source node
Trichy is at a distance of 150 from the source node
madurai is at a distance of 200 from the source node
Chennai is at a distance of 0 from the source node
Comments
Post a Comment