Last active
August 21, 2016 14:48
-
-
Save rishi93/7299a894d027e4b12da4a6db2fbbd373 to your computer and use it in GitHub Desktop.
Dijkstra's Shortest Path - SHPATH using C++
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <map> | |
#include <vector> | |
#include <queue> | |
using namespace std; | |
class Graph{ | |
public: | |
vector<pair<int,int> > adjList[10001]; | |
void addEdge(int city_index, int neighbor, int dist){ | |
adjList[city_index].push_back(make_pair(neighbor,dist)); | |
} | |
}; | |
//Implementing a min-heap using priority queue | |
struct cmp{ | |
bool operator()(const pair<int,int>& a, const pair<int,int>& b){ | |
if(a.second < b.second){ | |
return false; | |
} | |
else{ | |
return true; | |
} | |
} | |
}; | |
int dijkstra(Graph graph,int size, int src, int dst){ | |
//prioirty queue to retrieve least distance each time | |
priority_queue<pair<int,int>,vector<pair<int,int> >,cmp> pqi; | |
//To mark if already visited | |
map<int,int> visited; | |
int distances[10001]; | |
fill_n(distances,10001,1000000000); | |
int curr_dist; | |
vector<pair<int,int> > curr; | |
pqi.push(make_pair(src,0)); | |
while(visited.size() < size && pqi.empty() == false){ | |
while(visited.find(pqi.top().first) != visited.end()){ | |
pqi.pop(); | |
} | |
curr = graph.adjList[pqi.top().first]; | |
curr_dist = pqi.top().second; | |
distances[pqi.top().first] = curr_dist; | |
//Mark it as visited | |
visited[pqi.top().first] = 1; | |
pqi.pop(); | |
//Visit all the neighbors | |
for(int j=0; j<curr.size(); j++){ | |
if(visited.find(curr[j].first) == visited.end()){ | |
if(curr_dist + curr[j].second < distances[curr[j].first]){ | |
pqi.push(make_pair(curr[j].first,curr_dist+curr[j].second)); | |
} | |
} | |
} | |
} | |
return distances[dst]; | |
} | |
int main(){ | |
//For Fast IO | |
ios_base::sync_with_stdio(false); | |
cin.tie(NULL); | |
int t,n,city_index,no_of_neighbors,queries,a,b; | |
string city_name,city1,city2,emptyline; | |
map<string,int> city_dict; | |
cin>>t; | |
for(int testcase=0 ; testcase<t; testcase++){ | |
cin>>n; | |
Graph graph = Graph(); | |
for(int city_index=1; city_index<=n; city_index++){ | |
cin>>city_name; | |
cin>>no_of_neighbors; | |
city_dict[city_name] = city_index; | |
for(int i=0; i<no_of_neighbors; i++){ | |
cin>>a>>b; | |
graph.addEdge(city_index,a,b); | |
} | |
} | |
cin>>queries; | |
for(int i=0; i<queries; i++){ | |
cin>>city1>>city2; | |
cout<<dijkstra(graph,n,city_dict[city1],city_dict[city2])<<"\n"; | |
} | |
//Emptyline at end of each testcase | |
getline(cin,emptyline); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment