Find the paths between two given nodes?
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 ]
*/
Solution 3
Dijkstra's algorithm applies more to weighted paths and it sounds like the poster was wanting to find all paths, not just the shortest.
For this application, I'd build a graph (your application sounds like it wouldn't need to be directed) and use your favorite search method. It sounds like you want all paths, not just a guess at the shortest one, so use a simple recursive algorithm of your choice.
The only problem with this is if the graph can be cyclic.
With the connections:
- 1, 2
- 1, 3
- 2, 3
- 2, 4
While looking for a path from 1->4, you could have a cycle of 1 -> 2 -> 3 -> 1.
In that case, then I'd keep a stack as traversing the nodes. Here's a list with the steps for that graph and the resulting stack (sorry for the formatting - no table option):
current node (possible next nodes minus where we came from) [stack]
- 1 (2, 3) [1]
- 2 (3, 4) [1, 2]
- 3 (1) [1, 2, 3]
- 1 (2, 3) [1, 2, 3, 1] //error - duplicate number on the stack - cycle detected
- 3 () [1, 2, 3] // back-stepped to node three and popped 1 off the stack. No more nodes to explore from here
- 2 (4) [1, 2] // back-stepped to node 2 and popped 1 off the stack.
- 4 () [1, 2, 4] // Target node found - record stack for a path. No more nodes to explore from here
- 2 () [1, 2] //back-stepped to node 2 and popped 4 off the stack. No more nodes to explore from here
- 1 (3) [1] //back-stepped to node 1 and popped 2 off the stack.
- 3 (2) [1, 3]
- 2 (1, 4) [1, 3, 2]
- 1 (2, 3) [1, 3, 2, 1] //error - duplicate number on the stack - cycle detected
- 2 (4) [1, 3, 2] //back-stepped to node 2 and popped 1 off the stack
- 4 () [1, 3, 2, 4] Target node found - record stack for a path. No more nodes to explore from here
- 2 () [1, 3, 2] //back-stepped to node 2 and popped 4 off the stack. No more nodes
- 3 () [1, 3] // back-stepped to node 3 and popped 2 off the stack. No more nodes
- 1 () [1] // back-stepped to node 1 and popped 3 off the stack. No more nodes
- Done with 2 recorded paths of [1, 2, 4] and [1, 3, 2, 4]
Solution 4
The original code is a bit cumbersome and you might want to use the collections.deque instead if you want to use BFS to find if a path exists between 2 points on the graph. Here is a quick solution I hacked up:
Note: this method might continue infinitely if there exists no path between the two nodes. I haven't tested all cases, YMMV.
from collections import deque
# a sample graph
graph = {'A': ['B', 'C','E'],
'B': ['A','C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F','D'],
'F': ['C']}
def BFS(start, end):
""" Method to determine if a pair of vertices are connected using BFS
Args:
start, end: vertices for the traversal.
Returns:
[start, v1, v2, ... end]
"""
path = []
q = deque()
q.append(start)
while len(q):
tmp_vertex = q.popleft()
if tmp_vertex not in path:
path.append(tmp_vertex)
if tmp_vertex == end:
return path
for vertex in graph[tmp_vertex]:
if vertex not in path:
q.append(vertex)
Solution 5
In Prolog (specifically, SWI-Prolog)
:- use_module(library(tabling)).
% path(+Graph,?Source,?Target,?Path)
:- table path/4.
path(_,N,N,[N]).
path(G,S,T,[S|Path]) :-
dif(S,T),
member(S-I, G), % directed graph
path(G,I,T,Path).
test:
paths :- Graph =
[ 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
],
findall(Path, path(Graph,1,7,Path), Paths),
maplist(writeln, Paths).
?- paths.
[1,2,3,6,7]
[1,2,5,6,7]
true.
Related videos on Youtube
Jamie Sandalls
Updated on April 05, 2020Comments
-
Jamie Sandalls about 4 years
I want to force version control in Word documents as our documents are downloaded to work on locally, then re-uploaded.
I had the idea of embedding a macro that runs when a document is closed, presenting an input box, for name/date/summary of changes. This text is added to a hidden bookmark, that can be viewed if there are any version control doubts.
When I share this macro enabled document, saving the file becomes an endless loop. The SaveAs dialog keeps appearing when you click save, and no changes are saved. It works on the system that created the macro.
Reattaching the document template stops this issue, but it would be impractical to expect every user to do this for every document.
Any thoughts on why this save issue occurs, or a more elegant solution?
Private Sub Document_Close() Dim MyInput As String Dim oRng As Word.Range MyInput = InputBox("Please input your name, the date, and a brief summary of your edits.", "Revision Control", "Name: Date: Summary:") Set oRng = ActiveDocument.Bookmarks("revcontrol").Range oRng.Text = ActiveDocument.Bookmarks("revcontrol").Range.Text & vbNewLine & MyInput ActiveDocument.Bookmarks.Add "revcontrol", oRng oRng.Font.Hidden = True lbl_Exit: Exit Sub End Sub
-
yesraaj about 15 yearsis the implementation in question is ok for breadth first search?
-
Christoph about 15 yearsThis outputs every path, not just every simple one. For an undirected graph or a cyclic directed graph the code will create paths of increasing length, eventually resulting in a call-stack overflow. It should check whether current is in previous, and stop recursion if it is.
-
Konrad Rudolph about 15 yearsI'm no Python expert: does the
not in
operator really exist? Other than that, the code looks OK at a cursory glance. You can remove thenew_path = []
statement, though. Also, you can create the queue inside the method and remove it as a parameter. -
yesraaj about 15 yearsI am just going to convert this to c++ and use it.. Thanks for your input
-
prashantitis almost 10 years:can you tell what would be the complexity of the above code??
-
Kehlin Swain about 9 yearsDid you import this graph from a input text file
-
arslan about 8 yearswhat is the time complexity of this algorithm? O(n!)?
-
Federico Gentile almost 8 yearsHe doesn't need the shortest path, he needs to "Find the paths between two given nodes".
-
Sameer about 7 yearsIs it absolutely necessary for this to be a BFS, can the same not be achieved through recursive DFS while maintaining a list of all the visited nodes?
-
Konrad Rudolph about 7 years@Sameer You can also use DFS, yes.
-
Shayan Amani over 6 yearsVery helpful! Thumbs up.