Skip to content

Instantly share code, notes, and snippets.

@shahril96
Created July 3, 2016 14:49
Show Gist options
  • Save shahril96/1b51f55821e19fc88174f060e826b569 to your computer and use it in GitHub Desktop.
Save shahril96/1b51f55821e19fc88174f060e826b569 to your computer and use it in GitHub Desktop.
Using Dijkstra's algorithm to find the shortest path between 2 vertices inside a graph
/*
* references
*
* 1) http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
* 2) http://home.cse.ust.hk/faculty/golin/COMP271Sp03/Notes/MyL09.pdf
*
*/
#include <iostream>
#include <set>
#include <vector>
#include <map>
#include <utility>
#include <climits>
using namespace std;
struct Info {
int weight;
vector<int> vertices;
};
int main() {
int V, E;
int src, dst;
cin >> V >> E;
set<int> vertices;
map<int, vector<pair<int,int> > > edges;
for(int i = 0; i < E; i++) {
int v, u, w;
cin >> v >> u >> w;
edges[v].push_back(make_pair(u,w));
edges[u].push_back(make_pair(v,w));
vertices.insert(v);
vertices.insert(u);
}
// all input
// ready for an action!
// S = included vertices
set<int> S;
// Q = not yet included vertices
set<int> Q(vertices);
map<int, Info> cost;
for(auto v : vertices) {
Info info;
info.weight = INT_MAX;
cost[v] = info;
}
S.insert(0);
Q.erase(Q.find(0));
cost[0].weight = 0;
// process while remaining set isn't empty
while(Q.size() > 0) {
// find cost for all included vertices's adjacences
for(auto s : S) {
for(auto e : edges[s]) {
// s = v
// e.first = u
// e.second = w
// ignore if adjacent vertex is already
// inside included set
if(S.find(e.first) == S.end()) {
int total_cost = cost[s].weight + e.second;
if(total_cost < cost[e.first].weight) {
cost[e.first].weight = total_cost;
// copy vector of vertices to reach `u`
cost[e.first].vertices = cost[s].vertices;
cost[e.first].vertices.push_back(s);
}
}
}
}
int min_index = INT_MAX;
int min_cost = INT_MAX;
// find min cost for all adjacences
for(auto c : cost) {
// ignore vertex that already inside included set
if(S.find(c.first) == S.end()) {
if(c.second.weight < min_cost) {
min_index = c.first;
min_cost = c.second.weight;
}
}
}
// found vertex with minimum cost
// insert into already included set
// delete from remaining set
S.insert(min_index);
Q.erase(Q.find(min_index));
}
cout << "\n Node->Node\tPath\t\t\tWeight\n\n";
for(int i = 0; i < V; i++) {
cout << ' ' << 0 << " -> " << i << "\t\t";
for(auto v : cost[i].vertices) {
cout << v << ' ';
}
cout << i << "\t\t\t" << cost[i].weight << endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment