Finding the shortest path with topological sort in Directed Acyclic Graph
khandoker anan
Introduction
In a directed acyclic graph (DAG), a topological sort is a linear ordering of the vertices such that for every directed edge, the vertex u comes before v in the ordering. This ordering can be used to find the shortest path between two vertices in the DAG.
To find the shortest path between two vertices s and t, We can perform a modified version of Dijkstra's algorithm in a Directed Acyclic Graph with the help of topological sort. First, we initialize the distance to s as 0 and the distance to all other vertices as infinity. Then, we perform a topological sort of the graph and visit each vertex in the sorted order.
For each visited vertex u, we examine each of its outgoing edges (u, v). If the distance to u plus the weight of (u, v) is less than the current distance to v, we update the distance to v. At the end of the algorithm, the distance to t will give us the shortest path from s to t.
This algorithm works because the topological sort ensures that we always visit vertices in the correct order. Specifically, if we visit u before v, we know that there can be no path from v to u, so we can safely update the distance to v based on the distance to u.
Overall, using a topological sort to find the shortest path in a DAG is an efficient way to solve this problem, with a time complexity of O(V + E), where V is the number of vertices and E is the number of edges in the graph.
C++ code for topological sort where every vertex holds a string:
class Graph {
ll nodes;
map <string,vector<string>> adj;
map <string, bool > visited;
map <pair<string, string>, ll > wgt;
public:
Graph (ll nodes) {
this->nodes = nodes;
}
void addEdge (string u, string v, ll weight) {
wgt [make_pair(u,v)] = weight;
if (v != "") {
adj[u].pb(v);
visited[u] = false;
visited[v] = false;
}else {
adj[u];
visited[u] = false;
}
}
vector<string> tSort;
void tsort (string u) {
visited [u] = true;
for (auto i : adj[u]) {
if (visited[i] == false) {
tsort(i);
}
}
tSort.insert(tSort.begin(), u);
}
}
Algorithm for topological sort
0. toposort(u):
1. visited[u] = true
2. for all the adjacency vertex i of adj[u]:
3. if visited [i] is not true
4. toposort(i)
5. end if
6. end for
5. insert u in a linkedlist 'topolist' from front
We can efficiently solve the single source shortest path problem using topological sort in a directed acyclic graph. The idea is described above. So, let's start writing the algorithm for it.
Algorithm for DAG single source shortest path with the help of topological sort
0. single_source_shortest_path_dag (source, topolist, weight, adj):
1. for each vertex i in topolist:
2. distance [i] = INFINITY
3. predecessor [i] = NULL
4. end for
5. distance[source] = 0
6. for each vertex i in topolist:
7. for each adjacent vertex j in adj[i]:
8. if distance[i] + weight[(i,j)] < distance[j]:
9. distance [j] = distance[i] + weight[(i,j)]
10. predecessor [j] = i
11. end if
12. end for
13. end for
// Now using the distance and predecessor we can measure distance from the single source and track the path from source to destination
Problem 1
Mr. Bombasta is an alien and is confused about how to dress up like a human being. So he needs to know the order for dressing up. And he has a cost to pick up dresses. Tell him the shortest path from picking up other things if he starts with underwear. Here is the graph of the dresses:
Think for a while and solve the problem. Though I have attached the solution to this article, you should try to solve the problem yourself.
Solution:
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
#define INF 10e9
class Graph {
ll nodes;
map <string,vector<string>> adj;
map <string, bool > visited;
map <pair<string, string>, ll > wgt;
public:
Graph (ll nodes) {
this->nodes = nodes;
}
void addEdge (string u, string v, ll weight) {
wgt [make_pair(u,v)] = weight;
if (v != "") {
adj[u].pb(v);
visited[u] = false;
visited[v] = false;
}else {
adj[u];
visited[u] = false;
}
}
vector<string> tSort;
void tsort (string u) {
visited [u] = true;
for (auto i : adj[u]) {
if (visited[i] == false) {
tsort(i);
}
}
tSort.insert(tSort.begin(), u);
}
void printTopology () {
for (auto i : visited) {
i.second = false;
}
tSort.clear();
cout << "choose as source by order: ";
while (tSort.size() < nodes) {
string source = "";
int flag = 0;
for (auto i : visited) {
if (i.second == false) {
source = i.first;
flag = 1;
break;
}
}
if (flag) {
cout << "'" << source << "' " << endl;
tsort(source);
}else {
break;
}
}
cout << endl << endl;
cout << "Topological order: " << endl;
int c= 1;
for (auto i: tSort) {
cout << c <<". " << i << endl;
c++;
}
cout << endl;
for (auto i: visited) {
i.second = false;
}
}
map <string, pair <ll, string> > single_source_shortest_path_dag(string s) {
printTopology();
map <string, pair<ll, string>> res;
for (auto i : tSort ) {
res[i] = make_pair(INF, "NULL");
}
res[s] = make_pair(0, "NULL");
for (auto i: tSort) {
for (auto j : adj[i]) {
if (res[i].first + wgt [make_pair(i,j)] < res[j].first) {
res[j].first = res[i].first + wgt [make_pair(i,j)];
res[j].second = i;
}
}
}
return res;
}
};
void solve () {
Graph g(8);
g.addEdge("socks", "shoes", 3);
g.addEdge ("shoes", "", 0);
g.addEdge("underwear", "socks", 2);
g.addEdge("underwear", "pants", 6);
g.addEdge("pants", "belt", 5);
g.addEdge("pants", "shoes", 4);
g.addEdge("shirt", "belt", 7);
g.addEdge("shirt", "tie", 8);
g.addEdge("tie", "jacket", 9);
g.addEdge("jacket", "", 0);
g.addEdge("socks", "shoes", 3);
auto ans = g.single_source_shortest_path_dag("underwear");
cout << "shortest path list: " << endl;
for (auto i : ans) {
cout << i.first << ": " << i.second.first << ", " << i.second.second << endl;
}
cout << endl << endl;
cout << "shortest path from each destination: " << endl;
for (auto i : ans) {
cout << i.first << "(" << i.second.first << "): ";
stack <pair<string, ll>> st;
if (i.second.first == INF) {
cout << "N/A" << endl;
continue;
}
if (i.second.first == 0) {
cout << "No route needed" << endl;
continue;
}
string route = i.second.second;
while (ans[route].second != "NULL") {
st.push(make_pair(route, ans[route].first));
route = ans[route].second;
}
st.push(make_pair(route, ans[route].first));
while (!st.empty()) {
cout << st.top().first << "(" << st.top().second<< ") -> ";
st.pop();
}
cout << i.first << "(" << i.second.first << ")" << endl;
}
}
int main () {
solve ();
return 0;
}
Problem 2
http://www.spoj.com/problems/TOPOSORT/
Problem 3
https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=60
Problem 4
UVA 200 - Rare Order [difficulty: easy]
Problem 5
Subscribe to my newsletter
Read articles from khandoker anan directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by