#include <bits/stdc++.h>
using namespace std;
// Number of vertices in the graph
#define N 8
// data structure to store graph edges
struct Edge {
int src, dest, weight;
} ;
// class to represent a graph object
class Graph
{
public :
// A array of vectors to represent adjacency list
vector< Edge> adjList[ N] ;
// Constructor
Graph( vector< Edge> edges)
{
// add edges to the directed graph
for ( unsigned i = 0 ; i < edges.size ( ) ; i++ )
{
int src = edges[ i] .src ;
int dest = edges[ i] .dest ;
int weight = edges[ i] .weight ;
adjList[ src] .push_back ( { src, dest, weight} ) ;
}
}
} ;
// Perform DFS on graph and set departure time of all
// vertices of the graph
int DFS( Graph const & graph, int v, vector< bool >
& discovered, vector< int > & departure, int & time )
{
// mark current node as discovered
discovered[ v] = true ;
// set arrival time - not needed
// time++;
// do for every edge (v -> u)
for ( Edge e : graph.adjList [ v] )
{
int u = e.dest ;
// u is not discovered
if ( ! discovered[ u] )
DFS( graph, u, discovered, departure, time ) ;
}
// ready to backtrack
// set departure time of vertex v
departure[ time ] = v;
time ++ ;
}
// The function performs topological sort on a given DAG
// and then finds out the longest distance of all vertices
// from given source by running one pass of Bellman-Ford
// algorithm on edges of vertices in topological order
void findLongestDistance( Graph const & graph, int source)
{
// departure[] stores vertex number having its depature
// time equal to the index of it
vector< int > departure( N, - 1 ) ;
// stores vertex is discovered or not
vector< bool > discovered( N) ;
int time = 0 ;
// perform DFS on all undiscovered vertices
for ( int i = 0 ; i < N; i++ )
if ( ! discovered[ i] )
DFS( graph, i, discovered, departure, time ) ;
vector< int > cost( N, INT_MAX ) ;
cost[ source] = 0 ;
// Process the vertices in topological order i.e. in order
// of their decreasing departure time in DFS
for ( int i = N - 1 ; i >= 0 ; i-- )
{
// for each vertex in topological order,
// relax cost of its adjacent vertices
int v = departure[ i] ;
for ( Edge e : graph.adjList [ v] )
{
// edge e from v to u having weight w
int u = e.dest ;
int w = e.weight * - 1 ; // negative the weight of edge
// if the distance to the destination u can be shortened by
// taking the edge vu, then update cost to the new lower value
if ( cost[ v] ! = INT_MAX && cost[ v] + w < cost[ u] )
cost[ u] = cost[ v] + w;
}
}
// print longest paths
for ( int i = 0 ; i < N; i++ )
{
cout << "\n Longest distance of source vertex " << source <<
" to vertex " << i << " is " << setw( 2 ) << cost[ i] * - 1 ;
}
}
int main( )
{
// vector of graph edges as per above diagram
vector< Edge> edges =
{
{ 0 , 6 , 2 } , { 1 , 2 , - 4 } , { 1 , 4 , 1 } , { 1 , 6 , 8 } , { 3 , 0 , 3 } , { 3 , 4 , 5 } ,
{ 5 , 1 , 2 } , { 7 , 0 , 6 } , { 7 , 1 , - 1 } , { 7 , 3 , 4 } , { 7 , 5 , - 4 }
} ;
// create a graph from edges
Graph graph( edges) ;
// source vertex
int source = 7 ;
// find Longest distance of all vertices from given source
findLongestDistance( graph, source) ;
return 0 ;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBOdW1iZXIgb2YgdmVydGljZXMgaW4gdGhlIGdyYXBoCiNkZWZpbmUgTiA4CgovLyBkYXRhIHN0cnVjdHVyZSB0byBzdG9yZSBncmFwaCBlZGdlcwpzdHJ1Y3QgRWRnZSB7CglpbnQgc3JjLCBkZXN0LCB3ZWlnaHQ7Cn07CgovLyBjbGFzcyB0byByZXByZXNlbnQgYSBncmFwaCBvYmplY3QKY2xhc3MgR3JhcGgKewpwdWJsaWM6CQoJLy8gQSBhcnJheSBvZiB2ZWN0b3JzIHRvIHJlcHJlc2VudCBhZGphY2VuY3kgbGlzdAoJdmVjdG9yPEVkZ2U+IGFkakxpc3RbTl07CgoJLy8gQ29uc3RydWN0b3IKCUdyYXBoKHZlY3RvcjxFZGdlPiBlZGdlcykKCXsKCQkvLyBhZGQgZWRnZXMgdG8gdGhlIGRpcmVjdGVkIGdyYXBoCgkJZm9yKHVuc2lnbmVkIGkgPSAwOyBpIDwgZWRnZXMuc2l6ZSgpOyBpKyspCgkJewoJCQlpbnQgc3JjID0gZWRnZXNbaV0uc3JjOwoJCQlpbnQgZGVzdCA9IGVkZ2VzW2ldLmRlc3Q7CgkJCWludCB3ZWlnaHQgPSBlZGdlc1tpXS53ZWlnaHQ7CgoJCQlhZGpMaXN0W3NyY10ucHVzaF9iYWNrKHtzcmMsIGRlc3QsIHdlaWdodH0pOwoJCX0KCX0KfTsKCi8vIFBlcmZvcm0gREZTIG9uIGdyYXBoIGFuZCBzZXQgZGVwYXJ0dXJlIHRpbWUgb2YgYWxsIAovLyB2ZXJ0aWNlcyBvZiB0aGUgZ3JhcGgKaW50IERGUyhHcmFwaCBjb25zdCAmZ3JhcGgsIGludCB2LCB2ZWN0b3I8Ym9vbD4gCgkmZGlzY292ZXJlZCwgdmVjdG9yPGludD4gJmRlcGFydHVyZSwgaW50JiB0aW1lKQp7CgkvLyBtYXJrIGN1cnJlbnQgbm9kZSBhcyBkaXNjb3ZlcmVkCglkaXNjb3ZlcmVkW3ZdID0gdHJ1ZTsKCgkvLyBzZXQgYXJyaXZhbCB0aW1lIC0gbm90IG5lZWRlZAoJLy8gdGltZSsrOwoKCS8vIGRvIGZvciBldmVyeSBlZGdlICh2IC0+IHUpCglmb3IgKEVkZ2UgZSA6IGdyYXBoLmFkakxpc3Rbdl0pCgl7CgkJaW50IHUgPSBlLmRlc3Q7CgkJLy8gdSBpcyBub3QgZGlzY292ZXJlZAoJCWlmICghZGlzY292ZXJlZFt1XSkKCQkJREZTKGdyYXBoLCB1LCBkaXNjb3ZlcmVkLCBkZXBhcnR1cmUsIHRpbWUpOwoJfQoJCgkvLyByZWFkeSB0byBiYWNrdHJhY2sKCS8vIHNldCBkZXBhcnR1cmUgdGltZSBvZiB2ZXJ0ZXggdgoJZGVwYXJ0dXJlW3RpbWVdID0gdjsKCXRpbWUrKzsKfQoKLy8gVGhlIGZ1bmN0aW9uIHBlcmZvcm1zIHRvcG9sb2dpY2FsIHNvcnQgb24gYSBnaXZlbiBEQUcgCi8vIGFuZCB0aGVuIGZpbmRzIG91dCB0aGUgbG9uZ2VzdCBkaXN0YW5jZSBvZiBhbGwgdmVydGljZXMgCi8vIGZyb20gZ2l2ZW4gc291cmNlIGJ5IHJ1bm5pbmcgb25lIHBhc3Mgb2YgQmVsbG1hbi1Gb3JkIAovLyBhbGdvcml0aG0gb24gZWRnZXMgb2YgdmVydGljZXMgaW4gdG9wb2xvZ2ljYWwgb3JkZXIKdm9pZCBmaW5kTG9uZ2VzdERpc3RhbmNlKEdyYXBoIGNvbnN0JiBncmFwaCwgaW50IHNvdXJjZSkKewoJLy8gZGVwYXJ0dXJlW10gc3RvcmVzIHZlcnRleCBudW1iZXIgaGF2aW5nIGl0cyBkZXBhdHVyZQoJLy8gdGltZSBlcXVhbCB0byB0aGUgaW5kZXggb2YgaXQKCXZlY3RvcjxpbnQ+IGRlcGFydHVyZShOLCAtMSk7CgoJLy8gc3RvcmVzIHZlcnRleCBpcyBkaXNjb3ZlcmVkIG9yIG5vdAoJdmVjdG9yPGJvb2w+IGRpc2NvdmVyZWQoTik7CglpbnQgdGltZSA9IDA7CiAKCS8vIHBlcmZvcm0gREZTIG9uIGFsbCB1bmRpc2NvdmVyZWQgdmVydGljZXMKCWZvcihpbnQgaSA9IDA7IGkgPCBOOyBpKyspCgkJaWYoIWRpc2NvdmVyZWRbaV0pCgkJCURGUyhncmFwaCwgaSwgZGlzY292ZXJlZCwgZGVwYXJ0dXJlLCB0aW1lKTsKCQoJdmVjdG9yPGludD4gY29zdChOLCBJTlRfTUFYKTsKCWNvc3Rbc291cmNlXSA9IDA7CgkKCS8vIFByb2Nlc3MgdGhlIHZlcnRpY2VzIGluIHRvcG9sb2dpY2FsIG9yZGVyIGkuZS4gaW4gb3JkZXIgCgkvLyBvZiB0aGVpciBkZWNyZWFzaW5nIGRlcGFydHVyZSB0aW1lIGluIERGUyAKCWZvcihpbnQgaSA9IE4gLSAxOyBpID49IDA7IGktLSkKCXsKCQkvLyBmb3IgZWFjaCB2ZXJ0ZXggaW4gdG9wb2xvZ2ljYWwgb3JkZXIsIAoJCS8vIHJlbGF4IGNvc3Qgb2YgaXRzIGFkamFjZW50IHZlcnRpY2VzCgkJaW50IHYgPSBkZXBhcnR1cmVbaV07CgkJZm9yIChFZGdlIGUgOiBncmFwaC5hZGpMaXN0W3ZdKQoJCXsKCQkJLy8gZWRnZSBlIGZyb20gdiB0byB1IGhhdmluZyB3ZWlnaHQgdwkJCgkJCWludCB1ID0gZS5kZXN0OwoJCQlpbnQgdyA9IGUud2VpZ2h0ICogLTE7CS8vIG5lZ2F0aXZlIHRoZSB3ZWlnaHQgb2YgZWRnZQoJCQkKCQkJLy8gaWYgdGhlIGRpc3RhbmNlIHRvIHRoZSBkZXN0aW5hdGlvbiB1IGNhbiBiZSBzaG9ydGVuZWQgYnkgCgkJCS8vIHRha2luZyB0aGUgZWRnZSB2dSwgdGhlbiB1cGRhdGUgY29zdCB0byB0aGUgbmV3IGxvd2VyIHZhbHVlCgkJCWlmIChjb3N0W3ZdICE9IElOVF9NQVggJiYgY29zdFt2XSArIHcgPCBjb3N0W3VdKQoJCQkJY29zdFt1XSA9IGNvc3Rbdl0gKyB3OwoJCX0KCX0KCQoJLy8gcHJpbnQgbG9uZ2VzdCBwYXRocwoJZm9yIChpbnQgaSA9IDA7IGkgPCBOOyBpKyspCgl7CgkJY291dCA8PCAiXG5Mb25nZXN0IGRpc3RhbmNlIG9mIHNvdXJjZSB2ZXJ0ZXggIiA8PCBzb3VyY2UgPDwKCQkJIiB0byB2ZXJ0ZXggIiA8PCBpIDw8ICIgaXMgIiA8PCBzZXR3KDIpIDw8IGNvc3RbaV0gKiAtMTsKCX0KfQoKaW50IG1haW4oKQp7CgkvLyB2ZWN0b3Igb2YgZ3JhcGggZWRnZXMgYXMgcGVyIGFib3ZlIGRpYWdyYW0KCXZlY3RvcjxFZGdlPiBlZGdlcyA9IAoJewoJCXswLCA2LCAyfSwgezEsIDIsIC00fSwgezEsIDQsIDF9LCB7MSwgNiwgOH0sIHszLCAwLCAzfSwgezMsIDQsIDV9LAoJCXs1LCAxLCAyfSwgezcsIDAsIDZ9LCB7NywgMSwgLTF9LCB7NywgMywgNH0sIHs3LCA1LCAtNH0KCX07CgoJLy8gY3JlYXRlIGEgZ3JhcGggZnJvbSBlZGdlcwoJR3JhcGggZ3JhcGgoZWRnZXMpOwoKCS8vIHNvdXJjZSB2ZXJ0ZXgKCWludCBzb3VyY2UgPSA3OwoJCgkvLyBmaW5kIExvbmdlc3QgZGlzdGFuY2Ugb2YgYWxsIHZlcnRpY2VzIGZyb20gZ2l2ZW4gc291cmNlCglmaW5kTG9uZ2VzdERpc3RhbmNlKGdyYXBoLCBzb3VyY2UpOwoKCXJldHVybiAwOwp9Cg==