Dijkstra's Algorithm(Priority- First Search)

Expand Post »

I have a question regarding Dijkstra's algorithm (priority-first search)

To be precise:

In Online library: Algorithms in Java, Part 5. 21.2 Dijkstra s Algorithm

The statement to reassign the weight of tree vertices to 0 is needed for a general PFS implementation but not for Dijkstra's algorithm, since the priorities of the vertices added to the SPT are nondecreasing

Note the Dijkstra's algorithm doesn't discuss about dealing with negative weights yet at that point.

What does priorities of the vertices(distances) added to the SPT are nondecreasing mean?

Does it mean distance s-v-t is greater than s-v

as only the edge weight or distance is positive ?

So, it cannot decrease and can only increase.

If so, why is reassigning the weight of tree vertices to 0 needed for a general PFS implementation ?