dijkstra (#16) - Preserving Dijkstra Tree (#120) - Message List

Preserving Dijkstra Tree

Hi,

I want to extract the shortest path assignments to all the intermediate nodes calculated in order arrive at the final shortest path. I assume these assignments must be stored in some temporary structure during the application of the Dijkstra algorithm, and I also assume I would have to change the source to preserve it.

I'm just starting to dig through the source, but can anyone give me some hints on where to look?

Thanks

psc23
03/07/08 18:26:43 (3 years ago)
Tree View Flat View (newer first) Flat View (older first)
  • Message #440

    I'm not sure, but I guess I know what you need.

    There is predecessors map which stores previous vertex for each visited vertex. After the algorithm reaches the target, we need to restore the shortest path using this map. We get a predecessor for the target vertex, then predecessor of predecessor etc.

    anton
    03/10/08 09:51:24 (3 years ago)
Tree View Flat View (newer first) Flat View (older first)