Skip to content

Instantly share code, notes, and snippets.

@rishi93
Last active August 21, 2016 14:48
Show Gist options
  • Save rishi93/7299a894d027e4b12da4a6db2fbbd373 to your computer and use it in GitHub Desktop.
Save rishi93/7299a894d027e4b12da4a6db2fbbd373 to your computer and use it in GitHub Desktop.
Dijkstra's Shortest Path - SHPATH using C++
#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