Member Avatar for Mavericks

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 ?

Edited by Mavericks because: n/a
  • 2 Contributors
  • 4 Replies
  • 499 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Mavericks
Member Avatar for Momerath

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.

Member Avatar for Mavericks

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.

Member Avatar for Momerath

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?

Member Avatar for Mavericks

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.