Page 1 of 1
finding all possible paths
Posted: Sun Nov 16, 2003 7:47 pm
by IBelieve
I need an algorithm that writes ALL possible paths between two points where an adjacency matrix is given. I have no idea how to do this.Maybe you guys can help me.
Thanks in advance!
Posted: Mon Nov 17, 2003 6:48 am
by anupam
after finding a particular by all pair sp make the path unreachable by any way (making one edge infinity) then try again untill you find all the path..
it will work good if you want all the paths between all the nodes..
otherwise use dijkstra..
hope it will help..
--
Anupam
Posted: Wed Dec 31, 2003 2:39 am
by [Bart-Simpson]
What I did was basically start on the vertex
start and go through each vertex till I reach vertex
end. When I get there, I know I've found a path. Since it does it recursively, It doesn't repeat paths
IF your graph as no cicles!!
This function is for undirected graphs and only prints the number of possible paths between two points, but is quite simple to make it print the paths themselfs.
[java]
public void allPaths(int start, int end)
{
for(int j=0; j<nVerts; j++)
{
if(j == end && adjMat[start][j])
result++;
else
if(adjMat[start][j])
allPaths(j, end);
}
}
[/java]
Hope this helps you.
