Finding all paths in directed graph with specific cost

Question

Suppose we have the directed, weighted graph. Our task is to find all paths beetween two vertices (source and destination) which cost is less or equal =< N. We visit every vertex only once. In later version I'd like to add a condition that the source can be the destination (we just make a loop).

I think it can be done with modified Dijkstra's algorithm, but I have no idea how implement such thing. Thanks for any help.

Answer 1

You could use recursive backtracking to solve this problem. Terminate your recursion when:

• You get to the destination
• You visit a node that was already visited
• Your path length exceeds N.

Pseudocode:

list curpath := {}
int dest, maxlen
def findPaths (curNode, dist):
    if curNode = dest:
        print curpath
        return
    if curNode is marked:
        return
    if dist > maxlen:
        return
    add curNode to curpath
    mark curNode
    for nextNode, edgeDist adjacent to curNode:
        findPaths(nextNode, dist + edgeDist)
    remove last element of curpath

Answer 2

You want to find all the paths from point A to point B in a directed graph, such as the distance from A to B is smaller than N, and allowing the possibility that A = B.

Dijkstra's algorithm is taylored to find the smallest path from one point to another in a graph, and drops many all the others along the way, so to speak. Because of this, it cannot be used to find all the paths, if we include paths which overlaps.

You can achieve your goal by doing a breadth first search in the graph, keeping each branch of the covering tree in its on stack (you will get an enormous amount of them if the nodes are very well connected), and stop at depth N. All the branches which have reached B are kept aside. Once depth N has been covered, you drop all the paths which didn't reach B. The remaining ones, as well as the one kept aside put together becomes your solutions.

You may choose to add the restriction of not having cycles in your paths, in which case you would have check at each step of the search if the newly reached node is already in the path covered so far, and prune that path if it is the case.

Here is some pseudo code:

function find_paths(graph G, node A):
list<path> L, L';

L := empty list;
push path(A) in L;
for i = 2 to N begin
   L' := empty list;
   for each path P in L begin
       if last node of P = B then push P in L'
       else
       for each successor S of last node in P begin
           if S not in P then
              path P' := P;
              push S in P';
              push P' in L';
           endif
       end
       endif
   end
   L := L';
end

for each path P in L begin
  if last node of P != B
  then remove P from L
  endif
end
return L;

Answer 3

I think a possible improvement (depending on the size of the problem and the maximum cost N) to the recursive backtracking algorithm suggested by jma127 would be to pre-compute the minimum distance of each node from the destination (shortest path tree), then append the following to the conditions tested to terminate your recursion:

• You get to the a node whose minimum distance from the destination is greater than the maximum cost N minus the distance travelled to reach the current node.

If one needs to run the algorithm several times for different sources and destinations, one could run, e.g., Johnson's algorithm at the beginning to create a matrix of the shortest paths between all pairs of nodes.