# Finding the shortest path with topological sort in Directed Acyclic Graph

### 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]