# 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, 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 != "") {
visited[u] = false;
visited[v] = false;
}else {
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, 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 != "") {
visited[u] = false;
visited[v] = false;
}else {
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 ("shoes", "", 0);

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]