Find the paths between two given nodes?
Say I have nodes connected in the below fashion, how do I arrive at the number of paths that exist between given points, and path details?
1,2 //node 1 and 2 are connected
2,3
2,5
4,2
5,11
11,12
6,7
5,6
3,6
6,8
8,10
8,9
Find the paths from 1 to 7:
Answer: 2 paths found and they are
1,2,3,6,7
1,2,5,6,7
implementation found here is nice I am going to use the same
Here is the snippet from the above link in python
# a sample graph
graph = {'A': ['B', 'C','E'],
'B': ['A','C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F','D'],
'F': ['C']}
class MyQUEUE: # just an implementation of a queue
def __init__(self):
self.holder = []
def enqueue(self,val):
self.holder.append(val)
def dequeue(self):
val = None
try:
val = self.holder[0]
if len(self.holder) == 1:
self.holder = []
else:
self.holder = self.holder[1:]
except:
pass
return val
def IsEmpty(self):
result = False
if len(self.holder) == 0:
result = True
return result
path_queue = MyQUEUE() # now we make a queue
def BFS(graph,start,end,q):
temp_path = [start]
q.enqueue(temp_path)
while q.IsEmpty() == False:
tmp_path = q.dequeue()
last_node = tmp_path[len(tmp_path)-1]
print tmp_path
if last_node == end:
print "VALID_PATH : ",tmp_path
for link_node in graph[last_node]:
if link_node not in tmp_path:
#new_path = []
new_path = tmp_path + [link_node]
q.enqueue(new_path)
BFS(graph,"A","D",path_queue)
-------------results-------------------
['A']
['A', 'B']
['A', 'C']
['A', 'E']
['A', 'B', 'C']
['A', 'B', 'D']
VALID_PATH : ['A', 'B', 'D']
['A', 'C', 'D']
VALID_PATH : ['A', 'C', 'D']
['A', 'E', 'F']
['A', 'E', 'D']
VALID_PATH : ['A', 'E', 'D']
['A', 'B', 'C', 'D']
VALID_PATH : ['A', 'B', 'C', 'D']
['A', 'E', 'F', 'C']
['A', 'E', 'F', 'C', 'D']
VALID_PATH : ['A', 'E', 'F', 'C', 'D']
Solution 1:
Breadth-first search traverses a graph and in fact finds all paths from a starting node. Usually, BFS doesn't keep all paths, however. Instead, it updates a prededecessor function π to save the shortest path. You can easily modify the algorithm so that π(n)
doesn't only store one predecessor but a list of possible predecessors.
Then all possible paths are encoded in this function, and by traversing π recursively you get all possible path combinations.
One good pseudocode which uses this notation can be found in Introduction to Algorithms by Cormen et al. and has subsequently been used in many University scripts on the subject. A Google search for “BFS pseudocode predecessor π” uproots this hit on Stack Exchange.
Solution 2:
For those who are not PYTHON expert ,the same code in C++
//@Author :Ritesh Kumar Gupta
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
vector<vector<int> >GRAPH(100);
inline void print_path(vector<int>path)
{
cout<<"[ ";
for(int i=0;i<path.size();++i)
{
cout<<path[i]<<" ";
}
cout<<"]"<<endl;
}
bool isadjacency_node_not_present_in_current_path(int node,vector<int>path)
{
for(int i=0;i<path.size();++i)
{
if(path[i]==node)
return false;
}
return true;
}
int findpaths(int source ,int target ,int totalnode,int totaledge )
{
vector<int>path;
path.push_back(source);
queue<vector<int> >q;
q.push(path);
while(!q.empty())
{
path=q.front();
q.pop();
int last_nodeof_path=path[path.size()-1];
if(last_nodeof_path==target)
{
cout<<"The Required path is:: ";
print_path(path);
}
else
{
print_path(path);
}
for(int i=0;i<GRAPH[last_nodeof_path].size();++i)
{
if(isadjacency_node_not_present_in_current_path(GRAPH[last_nodeof_path][i],path))
{
vector<int>new_path(path.begin(),path.end());
new_path.push_back(GRAPH[last_nodeof_path][i]);
q.push(new_path);
}
}
}
return 1;
}
int main()
{
//freopen("out.txt","w",stdout);
int T,N,M,u,v,source,target;
scanf("%d",&T);
while(T--)
{
printf("Enter Total Nodes & Total Edges\n");
scanf("%d%d",&N,&M);
for(int i=1;i<=M;++i)
{
scanf("%d%d",&u,&v);
GRAPH[u].push_back(v);
}
printf("(Source, target)\n");
scanf("%d%d",&source,&target);
findpaths(source,target,N,M);
}
//system("pause");
return 0;
}
/*
Input::
1
6 11
1 2
1 3
1 5
2 1
2 3
2 4
3 4
4 3
5 6
5 4
6 3
1 4
output:
[ 1 ]
[ 1 2 ]
[ 1 3 ]
[ 1 5 ]
[ 1 2 3 ]
The Required path is:: [ 1 2 4 ]
The Required path is:: [ 1 3 4 ]
[ 1 5 6 ]
The Required path is:: [ 1 5 4 ]
The Required path is:: [ 1 2 3 4 ]
[ 1 2 4 3 ]
[ 1 5 6 3 ]
[ 1 5 4 3 ]
The Required path is:: [ 1 5 6 3 4 ]
*/