2
Contributors
4
Replies
6
Views
6 Years
Discussion Span
Last Post by Mavericks
1

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.

0

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.

0

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?

0

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

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.