What graph traversal algorithm should I use for this?

Question

Hello, I need to traverse a directed graph in a certain way and I'm not sure the algorithm to use. Perhaps Stackoverflow can 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

Answer 1

Dijkstra's algorithm.

Answer 2

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

Answer 3

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

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

Answer 4

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.