17.Shortest_path in_DAG.md

Find shortest path between source to all the edges in a DAG

Thought Process: use Topo sort to find out the shortest distance between source to each vertex

As this is a weighted graph so we are going to store the edge weights in adjacency list using pair, i.e vector<pair<int, int>> adj[] , it will store the edge and it's weight

Steps:

• Find topo sort in a given DAG and store it in a stack
• Create a distance array and initialize it with infinity
• Assign the source of distance array to be zero.
• Run a loop until stack will become empty
• Pop elements one by one from a stack
• If that node is not visited then only Go to all the adjacent nodes of fetched element and update the distance array if dist[parent node] + distance of parent node to that < dist[it]

Time and space complexity

• Time complexity would be O(N+E) * 2 the first O(N+E) for finding the topo sort as we are using DFS to find the topo sort and 2nd O(N+E) because we are again implementing a BFS kind of algorithm to find the distance
• Space complexity would be O(2N) for stack and distance array
• If you'll use DFS then there will be auxilliary space complexity, i fyou'll use BFS then there will be no auxilliary space complexity

Intuition behind using topo sort here instead of simple bfs or dfs:

For all who are wondering the intution behind Topological sorting and why haven't we use simple DFS or BFS from the source node instead, lets say you want to do it using DFS. yes you can do it using DFS , but consider the case when you already updated a node's distance by a dfs() call and lets say its 7 and as it is DFS then its obvious that you also have updated all the nodes in its segment of DFS call . now you have reached to the same node from different dfs() call and now the distance is 4 , so in order to update all the nodes which were affected by the DFS call previously on the node considering distance as 7 , you now again have to do the same so that its updated with new min distance.Same is the scenario for the simple BFS approach.This multiple time calling DFS/BFS degrades the Time Complexity, hence Topological Ordering save you from that overhead as you already know which nodes will come after the current node , so you keep on updating it

---

When you use a bfs, you are not sure which is the starting point, hence it might happen you have to iterate in the queue many times, when you use topo sort, you are sure this is the first node which has no incoming nodes. Hence you start from the starting point, hence taking lesser amount of time.While using BFS, you are not sure if your source is the starting point or not, if it is not, then you will be taking extra turns.

Code

#include<bits/stdc++.h>
using namespace std;

void topoSort(int src, stack<int> &st, vector<int> &vis, vector<pair<int, int>> adj[]){
        vis[src] = 1;
        for(auto it:adj[src]){
                //to access the node we have to write it.first
                //as in the pair, first is node data, second is weight
                if(!vis[it.first]){
                        //the next node data which would be passed as source would be it.first
                        topoSort(it.first, st, vis, adj);
                }
        }
        st.push(src);
}
void findShortestPath(int v, int src, vector<pair<int, int>> adj[]){
        stack<int> st;
        vector<int> vis(v, 0);
        for(int i=0; i<v; i++){
                if(!vis[i]){
                        topoSort(i, st, vis, adj);
                }
        }
        int dist[v];
        for(int i=0; i<v; i++)
                dist[i] = INT_MAX;
        dist[src] = 0;
        while(!st.empty()){
                int node = st.top();
                st.pop();
                if(dist[node] != INT_MAX){
                        for(auto it : adj[node]){
                                //if the distance of parent from source + dist of current edge is less than the distance already stored in the dist array
                                //then update the dist array
                                if(dist[node] + it.second < dist[it.first]){ //for the name of the node you've to write it.first
                                        dist[it.first] = dist[node] + it.second;
                                }
                        }
                }
        }
        for(int i=0; i<v; i++)
                (dist[i] == INT_MAX) ? cout<<"Infinity " : cout<<dist[i]<<" ";
        cout<<endl;
}

int main(){
        int n, m;
        cin>>n>>m;

        vector<pair<int, int>> adj[n];
        for(int i=0; i<m; i++){
                int u, v, wt;
                cin>>u>>v>>wt;
                adj[u].push_back({v, wt});
        }
        int src = 0;
        findShortestPath(n, src, adj);
        return 0;
}