-
Notifications
You must be signed in to change notification settings - Fork 617
/
longest_path_in_directed_acyclic_graph.cpp
135 lines (101 loc) · 2.42 KB
/
longest_path_in_directed_acyclic_graph.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/*
* DAG--> Directed Acyclic Graph
* We will be given a Weighted Directed Acyclic Graph (DAG) and a source vertex 's' in it,
* we have to find the longest distances from 's' to all other vertices in the given graph.
* Concept Required--
1) Topological Sort
2) Graph will be Directed
*/
#include<bits/stdc++.h>
#define int long long int
#define pb push_back
#define mod 1000000007
using namespace std;
vector<int> order; // for maintaining order vector
// Implementing Topological Sort
void topo(int src,vector<int> &vis,vector<vector<pair<int,int> > > g){
vis[src] = 1;
for(auto x:g[src]){
if(!vis[x.first])
topo(x.first,vis,g);
}
order.push_back(src); // adding vertex to order vector when a particular vertex is leaving its stack frame
}
int32_t main() {
int v,e;
cin>>v>>e; // Input vertex and edges
int src;
cin>>src;
// input of a graph as a adjency list
vector<vector<pair<int,int> > > g(v);
for(int i=0;i<e;i++){
int x,y,w;
cin>>x>>y>>w;
g[x].push_back({y,w});
}
vector<int> vis(v,0); // maintaning a visited array
for(int i=0;i<v;i++){
if(!vis[i]){
topo(i,vis,g);
}
}
vector<int> dist(v); // distance vector containing maximum distance from source vertex to ith vertex
for(int i=0;i<v;i++) dist[i] = INT_MIN;
dist[src] = 0;
for(int i=v-1;i>=0;i--){
if(dist[order[i]]!=INT_MIN){
for(auto x:g[order[i]]){
int v = dist[x.first];
int w = x.second;
int u = dist[order[i]];
if(u + w > v)
dist[x.first] = u + w;
}
}
}
// printing all the maximum distance
for(int i=0;i<v;i++){
if(i!=src and dist[i]!=INT_MIN){
cout<<src<<" -> "<<i<<" = "<<dist[i]<<endl;
}
}
return 0;
}
/*
Test Cases--
Input 1:
6 7
1
0 1 5
1 5 5
5 3 2
3 2 20
4 2 10
5 2 50
1 4 2
Output 1:
1 -> 2 = 55
1 -> 3 = 7
1 -> 4 = 2
1 -> 5 = 5
Input 2:
7 8
0
0 1 1
1 2 5
2 6 10
2 5 12
2 3 4
3 5 20
3 4 15
4 6 2
Output 2:
0 -> 1 = 1
0 -> 2 = 6
0 -> 3 = 10
0 -> 4 = 25
0 -> 5 = 30
0 -> 6 = 27
Time Complexity-- O(V+E), where V = No. of Vertex and E = No. of Edges
Space Complexity-- O(V), where V = No. of vertex, (assuming input graph is given)
*/