What chart traversal algorithm should I use for this?

Question

I need to go through a directed graph in a certain way, and I'm not sure if the algorithm will be used. Maybe Stackoverflow can help.

Situation - I have a directed graph where the edges have a number associated with them. Suppose this number is the distance measured in feet, miles, ..., whatever. I would like to go from the beginning of the node and find all the edges that are at some certain distance from the beginning of the node

For example, I want to start from some node and cross the graph and find all the edges where I drove 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 will be edge-2, edge-5. Any thoughts on which workaround I should use / considering?

thank

Answer 1

I would choose Dijkstra's algorithm . Just stop when the path to the last labeled node is greater than defined.

Answer 2

Dijkstra's algorithm .

Answer 3

, , , NP-hard. , , .

, : D [v, k], v v k , . D [v, k] , D [v, k-1]. , 100, , 100.

Answer 4

I think you can use something similar to Dijkstra’s algorithm

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