Menu
I am working on an implementation of Dijkstra's Algorithm to retrieve the shortest path between interconnected nodes on a network of routes. I have the implementation working. It returns all the shortest paths to all the nodes when I pass the start node into the algorithm.
My question: How does one go about retrieving all possible paths from Node A to, say, Node G or even all possible paths from Node A and back to Node A?
676
Approach: Either Breadth First Search (BFS) or Depth First Search (DFS) can be used to find path between two vertices. Take the first vertex as a source in BFS (or DFS), follow the standard BFS (or DFS). If the second vertex is found in our traversal, then return true else return false.
The idea is to do Depth First Traversal of a given directed graph. Start the DFS traversal from the source. Keep storing the visited vertices in an array or HashMap say 'path[]'. If the destination vertex is reached, print the contents of path[].
Algorithm: Create a recursive function that takes index of node of a graph and the destination index. Keep a global or a static variable count to store the count. Keep a record of the nodes visited using a visited array and while returning mark the current node to be unvisited to discover other paths.
Finding all possible paths is a hard problem, since there are exponential number of simple paths. Even finding the kth shortest path [or longest path] are NP-Hard.
One possible solution to find all paths [or all paths up to a certain length] from s to t is BFS, without keeping a visited set, or for the weighted version - you might want to use uniform cost search
Note that also in every graph which has cycles [it is not a DAG] there might be infinite number of paths between s to t.
197
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
