CODEWITHSUNDEEP
algorithmgraph-theorypriority-queuedijkstra
Chris Stryczynski
Chris Stryczynski

Reputation: 34021

How do I keep track of the shortest paths in the Dijkstra algorithm when using a min-priority queue?

I'm trying to implement Dijkstra's algorithm with a priority queue.

From my understanding, "Dijkstra's algorithm" allows to to find the shortest 'paths', in that it will return a set of vertices that form the shortest path *.

From this answer here https://stackoverflow.com/a/20217659/1663462, as well as (Dijkstra's_algorithm#Algorithm) it seems I should be able implement it using just two datastructures: a graph and queue datastructure.

However, in my implementation using the two mentioned datastructures, when I finally reach the destination node, I don't have the vertices path stored? In other words I just have the shortest distance only (a single scalar value).

How is this meant to be kept track of? The only way I can think of is to use an additional datastructure - an array or hash map where the key would be the vertex and the value would be it's parent.

The actual question:

Is the additional datastructure necessary to achieve ("set of vertices that form the shortest path *")? If not, how do I determine the vertices?

Upvotes: 2

Views: 3233

Answers (3)

Stef
Stef

Reputation: 15525

Although it is possible to store additional information on the nodes while running Dijkstra's algorithm, it is not strictly necessary.

Indeed, it is possible to trace back a shortest path after running Dijkstra's algorithm, even if no additional information was stored on the nodes. The only information needed on each node is its distance from the source.

I will use the following notations:

  • s is the source vertex;
  • t is the destination vertex;
  • w(u,v) is the length of edge (u,v) between two vertices u and v (given with the graph);
  • d(v) is the length of the shortest path from source s to a vertex v (computed by Dijkstra).

If Dijkstra's algorithm was run correctly, then the following proposition must be true for all vertices v except the source:

  • Vertex v has at least one neighbour u such that d(v) = d(u) + w(u,v).

For every vertex v, call pred(v) that neighbour.

Then a shortest path can be constructed in reverse, starting from destination t, by following the pred vertices.

Upvotes: 0

Chris Stryczynski
Chris Stryczynski

Reputation: 34021

Yes the additional data structure is necessary, I did not find a way to do without it.

One get the shortest 'distance' without it between two vertices, but it will not include the list of vertices between the source and destination vertex.

Upvotes: 0

snakile
snakile

Reputation: 54541

You don't have to keep track of the whole path for each vertex as you've suggested. To produce the s-v paths themselves, the only thing you have to record for each vertex v is the edge that "discovered" it.

In other words, as a vertex v is being discovered by the algorithm, you record the edge (u,v) on which it achieved the value that minimized the distance from s.

Now, assuming you have the "discovering" edge for each vertex v in the graph, the path from s to v can be computed as follows: if (u,v) is the ("discovering") edge stored for v, then the shortest path from s to v is the path from s to u (which can be computed recursively), followed by the single edge (u,v).

So, to construct the shortest path from s to v, you start at vertex v, then you follow the edge stored for v in the reverse direction, and continue until you reach s.

Upvotes: 2

Related Questions