fork download
copy 
  1. #include <iostream>
  2. #include <list>
  3. #include <string>
  4. #include <vector>
  5. using namespace std;
  6. vector <string> v1 = {"Prague", "Helsinki", "Beijing", "Tokyo", "Jakarta","London", "New York"};
  7. vector <int> w = {};
  8. // A directed graph using
  9. // adjacency list representation
  10. class Graph {
  11.     int V; // No. of vertices in graph
  12.     list<int>* adj; // Pointer to an array containing adjacency lists
  13.     list<int>* adj_weights; // Pointer to an array containing adjacency lists
  14.  
  15.     // A recursive function used by printAllPaths()
  16.     void printAllPathsUtil(int, int, bool[], int[], int[], int&, int);
  17.  
  18. public:
  19.     Graph(int V); // Constructor
  20.     void addVertex(string name);
  21.     void addEdge(int u, int v, int weight);
  22.     void printAllPaths(int s, int d);
  23. };
  24.  
  25. Graph::Graph(int V)
  26. {
  27.     this->V = V;
  28.     adj = new list<int>[V];
  29.     adj_weights = new list<int>[V];
  30. }
  31. void Graph::addEdge(int u, int v, int weight)
  32. {
  33.     adj[u].push_back(v); // Add v to u’s list.
  34.     adj_weights[u].push_back(weight); // Add the weight of the path as well.
  35. }
  36.  
  37. // Prints all paths from 's' to 'd'
  38. void Graph::printAllPaths(int s, int d)
  39. {
  40.     // Mark all the vertices as not visited
  41.     bool* visited = new bool[V];
  42.     // Create an array to store paths
  43.     int* path = new int[V];
  44.     int* path_costs = new int[V];
  45.     int path_index = 0; // Initialize path[] and path_costs[] as empty
  46.  
  47.     // Initialize all vertices as not visited
  48.     for (int i = 0; i < V; i++)
  49.         visited[i] = false;
  50.  
  51.     // Call the recursive helper function to print all paths
  52.     // Note that we let cost = 0 since we don't have to move to the starting city
  53.     printAllPathsUtil(s, d, visited, path_costs, path, path_index, 0);
  54. }
  55.  
  56. // A recursive function to print all paths from 'u' to 'd'.
  57. // visited[] keeps track of vertices in current path.
  58. // path[] stores actual vertices and path_index is current
  59. // index in path[]
  60. void Graph::printAllPathsUtil(int u, int d, bool visited[], int path_costs[],
  61.                               int path[], int& path_index, int cost)
  62. {
  63.     // Mark the current node and store it in path[]
  64.     visited[u] = true;
  65.     path[path_index] = u;
  66.     path_costs[path_index] = cost;   // Save cost of this step
  67.     path_index++;
  68.     int sum = 0;
  69.     // If current vertex is same as destination, then print
  70.     // current path[]
  71.     if (u == d) {
  72.         for (int i = 0; i < path_index; i++){
  73.             sum += path_costs[i];   // Now add all the costs
  74.             cout << v1[path[i]] << " ";
  75.         }
  76.         cout << endl;
  77.         cout << "Total distance is: " << sum;
  78.         cout << endl;
  79.     }
  80.     else // If current vertex is not destination
  81.     {
  82.         // Recur for all the vertices adjacent to current vertex
  83.         // Now we loop over both adj and adj_weights
  84.         list<int>::iterator i, j;
  85.         for (i = adj[u].begin(), j = adj_weights[u].begin();
  86.              i != adj[u].end(); ++i, ++j)
  87.             if (!visited[*i])
  88.                 printAllPathsUtil(*i, d, visited, path_costs, path, 
  89.                                   path_index, *j);
  90.     }
  91.  
  92.     // Remove current vertex from path[] and mark it as unvisited
  93.     path_index--;
  94.     visited[u] = false;
  95. }
  96.  
  97. // Driver program
  98. int main()
  99. {
  100.     // Create a graph given in the above diagram
  101.     Graph g(7);
  102.  
  103.     g.addEdge(0, 1, 1845);
  104.     g.addEdge(0, 5, 1264);
  105.     g.addEdge(1, 3, 7815);
  106.     g.addEdge(2, 5, 8132); 
  107.     g.addEdge(2, 6, 11550);
  108.     g.addEdge(2, 3, 1303);
  109.     g.addEdge(3, 4, 5782);
  110.     g.addEdge(3, 6, 10838);
  111.     g.addEdge(4, 2, 4616);
  112.     g.addEdge(5, 3, 9566);
  113.     g.addEdge(6, 5, 5567);
  114.     int s = 0, d = 2;
  115.     cout << "Following are all different paths from " << v1[s] << " to " << v1[d] << endl;
  116.     g.printAllPaths(s, d);
  117.  
  118.     return 0;
  119.  
  120. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Following are all different paths from Prague to Beijing
Prague Helsinki Tokyo Jakarta Beijing 
Total distance is: 20058
Prague London Tokyo Jakarta Beijing 
Total distance is: 21228
https://ideone.com/xGju0y
language:
C++ (gcc 8.3)
created:
3 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!