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

```cpp
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

```bash
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

```bash
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:

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1683373233169/0844bd40-7394-4d63-bbef-25536931e40c.png align="center")

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:

```cpp
#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/](http://www.spoj.com/problems/TOPOSORT/)

### Problem 3

[https://onlinejudge.org/index.php?option=onlinejudge&page=show\_problem&problem=60](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=60)

### Problem 4

[UVA 200 - Rare Order \[difficulty: easy\]](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=136)

### Problem 5

[https://cses.fi/problemset/task/1679](https://cses.fi/problemset/task/1679)