What graph traversal algorithm should I use for this?

I need to traverse a directed graph in a certain way and I'm not sure the algorithm to use. Perhaps Stackoverflow ca开发者_开发技巧n help.

The situation - I have a directed graph where the edges have a number associated with them. Let's assume this number is a distance measured in feet, miles, ..., whatever. I'd like to traverse from a start node and find all edges that are some defined distance from the start node

For example, I want to start at some node and traverse the graph and find every edge where I've traveled 100 miles from the start. For example(2), start_node ---- edge-1(80 miles) ---> node(2) ---- edge-2(40 miles) ---> node(3) ---edge-3(50 miles) --- start_node ---- edge-4(40 miles) ---> node(4) ---- edge-5(70 miles) ---> node(5) ---edge-6(50 miles) ---

Starting at start_node and traveling 100 miles the answer would be edge-2, edge-5. Any thoughts on what traversal algorithm I should be using/considering?

Thanks

I would choose Dijkstra algorithm. Just stop when the path to the last marked node is more than defined.

Dijkstra's algorithm.

Assuming no edge can be traversed more than once, your problem is a generalization of the Longest path problem, which is NP-hard. Therefore, polynomial-time approaches like Dijkstra's algorithm won't work.

If your graph is not very large, you could do dynamic programming: a table D[v, k] that stores for each vertex v and each number of edges all possible distances from the root to v with k edges, plus all possible predecessors for each possible distance. D[v, k] can be filled in if D[v, k-1] is done. You repeat this until no distance is below 100 anymore, and then you can do backtracking from each vertex that has reached cost exactly 100.

i think you can use something similar to Dijkstra's algorithm

http://en.wikipedia.org/wiki/Dijkstra's_algorithm