fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Number of vertices in the graph
  5. #define N 8
  6.  
  7. // data structure to store graph edges
  8. struct Edge {
  9. 	int src, dest, weight;
  10. };
  11.  
  12. // class to represent a graph object
  13. class Graph
  14. {
  15. public:	
  16. 	// A array of vectors to represent adjacency list
  17. 	vector<Edge> adjList[N];
  18.  
  19. 	// Constructor
  20. 	Graph(vector<Edge> edges)
  21. 	{
  22. 		// add edges to the directed graph
  23. 		for(unsigned i = 0; i < edges.size(); i++)
  24. 		{
  25. 			int src = edges[i].src;
  26. 			int dest = edges[i].dest;
  27. 			int weight = edges[i].weight;
  28.  
  29. 			adjList[src].push_back({src, dest, weight});
  30. 		}
  31. 	}
  32. };
  33.  
  34. // Perform DFS on graph and set departure time of all 
  35. // vertices of the graph
  36. int DFS(Graph const &graph, int v, vector<bool> 
  37. 	&discovered, vector<int> &departure, int& time)
  38. {
  39. 	// mark current node as discovered
  40. 	discovered[v] = true;
  41.  
  42. 	// set arrival time - not needed
  43. 	// time++;
  44.  
  45. 	// do for every edge (v -> u)
  46. 	for (Edge e : graph.adjList[v])
  47. 	{
  48. 		int u = e.dest;
  49. 		// u is not discovered
  50. 		if (!discovered[u])
  51. 			DFS(graph, u, discovered, departure, time);
  52. 	}
  53.  
  54. 	// ready to backtrack
  55. 	// set departure time of vertex v
  56. 	departure[time] = v;
  57. 	time++;
  58. }
  59.  
  60. // The function performs topological sort on a given DAG 
  61. // and then finds out the longest distance of all vertices 
  62. // from given source by running one pass of Bellman-Ford 
  63. // algorithm on edges of vertices in topological order
  64. void findLongestDistance(Graph const& graph, int source)
  65. {
  66. 	// departure[] stores vertex number having its depature
  67. 	// time equal to the index of it
  68. 	vector<int> departure(N, -1);
  69.  
  70. 	// stores vertex is discovered or not
  71. 	vector<bool> discovered(N);
  72. 	int time = 0;
  73.  
  74. 	// perform DFS on all undiscovered vertices
  75. 	for(int i = 0; i < N; i++)
  76. 		if(!discovered[i])
  77. 			DFS(graph, i, discovered, departure, time);
  78.  
  79. 	vector<int> cost(N, INT_MAX);
  80. 	cost[source] = 0;
  81.  
  82. 	// Process the vertices in topological order i.e. in order 
  83. 	// of their decreasing departure time in DFS 
  84. 	for(int i = N - 1; i >= 0; i--)
  85. 	{
  86. 		// for each vertex in topological order, 
  87. 		// relax cost of its adjacent vertices
  88. 		int v = departure[i];
  89. 		for (Edge e : graph.adjList[v])
  90. 		{
  91. 			// edge e from v to u having weight w		
  92. 			int u = e.dest;
  93. 			int w = e.weight * -1;	// negative the weight of edge
  94.  
  95. 			// if the distance to the destination u can be shortened by 
  96. 			// taking the edge vu, then update cost to the new lower value
  97. 			if (cost[v] != INT_MAX && cost[v] + w < cost[u])
  98. 				cost[u] = cost[v] + w;
  99. 		}
  100. 	}
  101.  
  102. 	// print longest paths
  103. 	for (int i = 0; i < N; i++)
  104. 	{
  105. 		cout << "\nLongest distance of source vertex " << source <<
  106. 			" to vertex " << i << " is " << setw(2) << cost[i] * -1;
  107. 	}
  108. }
  109.  
  110. int main()
  111. {
  112. 	// vector of graph edges as per above diagram
  113. 	vector<Edge> edges = 
  114. 	{
  115. 		{0, 6, 2}, {1, 2, -4}, {1, 4, 1}, {1, 6, 8}, {3, 0, 3}, {3, 4, 5},
  116. 		{5, 1, 2}, {7, 0, 6}, {7, 1, -1}, {7, 3, 4}, {7, 5, -4}
  117. 	};
  118.  
  119. 	// create a graph from edges
  120. 	Graph graph(edges);
  121.  
  122. 	// source vertex
  123. 	int source = 7;
  124.  
  125. 	// find Longest distance of all vertices from given source
  126. 	findLongestDistance(graph, source);
  127.  
  128. 	return 0;
  129. }
  130.  
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Longest distance of source vertex 7 to vertex 0 is  7
Longest distance of source vertex 7 to vertex 1 is -1
Longest distance of source vertex 7 to vertex 2 is -5
Longest distance of source vertex 7 to vertex 3 is  4
Longest distance of source vertex 7 to vertex 4 is  9
Longest distance of source vertex 7 to vertex 5 is -4
Longest distance of source vertex 7 to vertex 6 is  9
Longest distance of source vertex 7 to vertex 7 is  0
https://ideone.com/OFyfnE
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!