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!
finding all possible paths
Moderator: Board moderators
finding all possible paths
When people agree with me I always feel that I must be wrong.
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
it will work good if you want all the paths between all the nodes..
otherwise use dijkstra..
hope it will help..
--
Anupam
"Everything should be made simple, but not always simpler"
-
[Bart-Simpson]
- New poster
- Posts: 1
- Joined: Wed Dec 31, 2003 2:27 am
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.
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.
Real programmers don't need comments... the code is obvious!