shortest path algorithm in a dag

Solutions on MaxInterview for shortest path algorithm in a dag by the best coders in the world

showing results for - "shortest path algorithm in a dag"
Clara
12 Jan 2020
1//Shortest path in DAG
2#include<bits/stdc++.h>
3using namespace std;
4void addedge(vector<pair<int,int>>adj[],int u,int v,int weight)
5{
6    adj[u].push_back(make_pair(v,weight));
7}
8void topo(int node,vector<pair<int,int>>adj[],int visited[],stack<int>&st)
9{
10    visited[node]=1;
11    for(auto it:adj[node])
12    {
13        if(!visited[it.first])
14        {
15            topo(it.first,adj,visited,st);
16        }
17    }
18    st.push(node);
19}
20void shortestpath(vector<pair<int,int>>adj[],int source,int n)
21{
22    int vist[n]={0};
23    stack<int>st;
24    for(int i=0;i<n;i++)
25    {
26        if(!vist[i])
27        {
28            topo(i,adj,vist,st);
29        }
30    }
31    int dist[n];
32    for(int i=0;i<n;i++)
33    {
34        dist[i]=INT_MAX;
35    }
36    dist[source]=0;
37    while(!st.empty())
38    {
39        int node=st.top();
40        st.pop();
41        if(dist[node!=INT_MAX])
42        {
43            for(auto it: adj[node])
44            {
45                if(dist[node]+it.second<dist[it.first])
46                {
47                    dist[it.first]=dist[node]+it.second;
48                }
49            }
50        }
51    }
52    for(int i=0;i<n;i++)
53    {
54        if(dist[i]==INT_MAX)
55        {
56            cout<<"imf"<<" ";
57        }
58        else
59        {
60            cout<<dist[i]<<" ";
61        }
62    }
63}
64int main()
65{
66    int vertex,edges;
67    cout<<"ENTER THE NUMBER OF VERTEX AND EDGES:"<<endl;
68    cin>>vertex>>edges;
69    vector<pair<int,int>>adj[vertex];
70    int a,b,w;
71    cout<<"ENTER THE LINKS:"<<endl;
72    for(int i=0;i<edges;i++)
73    {
74        cin>>a>>b>>w;
75        addedge(adj,a,b,w);
76    }
77    int src;
78    cout<<"ENTER THE NODE FROM WHICH SHORTEST PATH IS MEANT TO BE FOUND:"<<endl;
79    cin>>src;
80    shortestpath(adj,src,vertex);
81    return 0;
82}
83