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

To be precise:
In http://flylib.com/books/en/3.56.1.58/1/

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 ?

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

It means that the priorities aren't negative.

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.

Almost, it means that the distance s-v-t is the same or greater than s-v. Nondecreasing doesn't mean increasing.

Thanks Momerath. I agree, and understand now.

I still don't understand why reassigning weights of tree vertices to zero is needed for general PFS(Priority First search) implementation.

I can't imagine a situation where reassigning will be needed.

I can't find where it says that in that text you linked, so it's hard to explain their reasoning without knowing what it is :)

Maybe I'm just being blind, can you tell me where it says that?

I can't find where it says that in that text you linked, so it's hard to explain their reasoning without knowing what it is :)

Maybe I'm just being blind, can you tell me where it says that?

In
http://ptgmedia.pearsoncmg.com/images/0201361213/samplechapter/sedgewickch21.pdf

Program 21.1, has the following sentence:

The constructor is also a generalized graph search that implements
other PFS algorithms with other assignments to the priority P (see text).
* 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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.