Search⌘ K
Home
Courses
Algorithms for Coding Interviews in C++

Solution: Print all Paths Between Two Nodes

Explore how to print all paths between two nodes in a graph by applying recursive graph traversal techniques. Learn to identify paths from a source to a destination node and review the time complexity of these algorithms, enabling you to approach graph problems effectively in coding interviews.

We'll cover the following...

Solution: Graph Traversal

If we traverse the graph from the source using any graph traversal algorithm, we can tell whether such a traversal will lead us to the desired destination or not.

C++
#include "Graph.h"
void Graph::utilityFunction(int source, int destination, vector <bool>& visited, vector<int>& path, int & pathIndex) {
  visited[source] = true;
  path[pathIndex] = source;
  pathIndex++;
  if (source == destination) { // if destination reached print it
    for (int i = 0; i < pathIndex; i++)
      cout << path[i] << " ";
    cout << endl;
  } 
  else { //else keep on iterating
    list <int> ::iterator i;
    for (i = adjacencyList[source].begin(); i != adjacencyList[source].end(); ++i)
      if (visited[ * i] == false)
        utilityFunction( * i, destination, visited, path, pathIndex);
  }
  pathIndex--;
  visited[source] = false; // clear the visited tab of source
}
void Graph::printAllPaths(int source, int destination) {
  vector <bool> visited(this -> vertices, false);
  vector<int> path(this -> vertices);
  int pathIndex = 0;
  utilityFunction(source, destination, visited, path, pathIndex);
}
int main() {
  Graph g(9);
  g.addEdge(0, 1);
  g.addEdge(1, 2);
  g.addEdge(1, 5);
  g.addEdge(2, 3);
  g.addEdge(2, 4);
  g.addEdge(5, 3);
  g.addEdge(5, 6);
  g.addEdge(3, 6);
  g.addEdge(6, 7);
  g.addEdge(6, 8);
  g.addEdge(6, 4);
  g.addEdge(7, 8);
  int source = 0, destination = 6;
  cout << "Paths from " << source << " to " << destination << endl;
  g.printAllPaths(source, destination);
  return 0;
}

All we need to solve this problem is to simply traverse from ...