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