How to find the shortest path satisfying constraints on a graph

I'm trying to find the shortest path on a weighted graph given the constraint that the path must have a total distance less than some parameter (let's 开发者_如何学Pythonsay 1000).

I tried the following but I don't know why my code is wrong.

def directedDFS(digraph, start, end, maxTotalDist):
    visited = []
    if not (digraph.hasNode(start) and digraph.hasNode(end)):
        raise ValueError('Start or end not in graph.')
    path = [str(start)]
    if start == end:
        return path
    shortest = None
    for node in digraph.childrenOf(start):
        if (str(node) not in visited):
            visited = visited + [str(node)]
            firststep_distance = digraph.childrenOf(start)[node][0]
            firststep_outer_distance = digraph.childrenOf(start)[node][1]
            if (firststep_distance <= maxTotalDist):
                newPath = directedDFS(digraph, node, end, maxTotalDist-firststep_distance)
                if newPath == None:
                    continue
                if (shortest == None or TotalDistance(digraph,newPath) < TotalDistance(digraph,shortest)):
                    shortest = newPath
    if shortest != None:
        path = path + shortest
    else:
        path = None
    return path

Another thing is that I don't want to compare based on the distance of the path starting from the given node but based on the distance of the ENTIRE PATH from the original starting point. I don't know the best way to do that here though.

---

I really can't make heads or tails of the code you provided (firststep_distance? firststep_outer_distance?). Could you provide the name of the algorithm you're trying to implement?

If you're just making something up on the fly, and you're not doing with the goal of reinventing graph theory for educational purposes, I'd suggest looking up a standard shortest-path algorithm. If you can guarantee that your weights are non-negative, then the standard is Dijkstra's algorithm. Wikipedia will report an improved asymptotic runtime if you back it with a Fibonacci heap, but don't fall for that trap---apparently, Fibonacci heaps have horrible performance in practice.

If Dijkstra's isn't good enough, take a look into A*-search methods. Here, as in all algorithm questions, CLR is your best guide, but Wikipedia is damn close. Hope that helps!

---

I also can't really tell what's going on without more code or info, but this is concerning:

        if (firststep_distance <= maxTotalDist):
            newPath = directedDFS(digraph, node, end, maxTotalDist-firststep_distance)

If you are decreasing the maxTotalDistance in each recursive call, then firststep_distance (which I assume is the weight of the path) must be greater than the remaining distance, not less.