# Thread: Dijkstra's Algorithm(Priority- First Search)

1. 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 ?  2.

3. First I'd recommend you to check out Wikipedia article on Dijkstra's algorithm: Dijkstra's algorithm - Wikipedia, the free encyclopedia.

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

If you are talking about queue this means that multiple vertices with the same distance are allowed in the queue.

Consider the sequence: 1, 1, 2. It's neither descending, nor truly ascending. It's non-descending (aka nondecreasing).  4. Originally Posted by BlasW If you are talking about queue this means that multiple vertices with the same distance are allowed in the queue.
Consider the sequence: 1, 1, 2. It's neither descending, nor truly ascending. It's non-descending (aka nondecreasing).
Thank you so much for the response. I've read the wiki link. Explanation is lot better in that link.

Yes, the program makes use of the queue. - program 21.1
http://ptgmedia.pearsoncmg.com/image...gewickch21.pdf

1,1,2 makes sense but what about 1,0,2. In the case of 3,2,5 how does it satisfy the condition of non-decreasing?
Let us say SPT starts from vertex 0, and edges 0-9, 0- 11, 0-12
distance/weight - d/w

d(1) of 0-1

d(3) of (0-1-9) is added to SPT
d(2) of (0-1-11) is added to SPT
d(5) of (0-1-12) is added to SPT

Now, if those are the vertices added to the tree ,I can't say priorities of weights are in a non-decreasing (looking at d(3) and d(2))

Also, what is need to reassign weight of tree vertices to 0 in a PFS implementation?
Is there a situation where a PFS implementation needs assigning 0 to *tree* vertices?

For example, program 20.7 @ Read books online free: Algorithms in Java, Part 5. 20.3 Prim s Algorithm and Priority-First Search has priority First Search.
[Java] PFS - Pastebin.com
There is no need to assign any weight of tree vertices to zero in 20.7  5. 1,1,2 makes sense but what about 1,0,2. In the case of 3,2,5 how does it satisfy the condition of non-decreasing?
Let us say SPT starts from vertex 0, and edges 0-9, 0- 11, 0-12
distance/weight - d/w
In short, such sequence is impossible. This is not just queue but priority queue of vertices. In this queue priority is provisional distance of to the vertex. Such a queue arranges vertices, so when you enqueue vertex it's placed accordingly, and when you dequeue, you get vertex with highest priority(=shortest distance). Such a queue may be implemented in array, binary heap or Fibonacci heap. See Dijkstra's algorithm - Wikipedia, the free encyclopedia.  6. True . I agree.
I was thinking the same but I'm confused when the statement says
'priorities of vertices added to the SPT (Shortest Path Tree) is non decreasing'
I'm confused as I'm thinking about the distances to be added to the SPT before enqueue operation.
10 get added to SPT for vertex 3
20 gets added to SPT for vertex 2
15 gets added(replaces) for vertex 2 (as 15<20)
30 gets added for vertex 4

So, the priorities (weights) of the vertices added one after the other to the SPT can be any random values.
It doesn't have to be an order before enqueue.

1
\
2------7
\
3
Now 1-2 gets enqueued with d=10
2-7 enqueued with d= 30
2-3 with d= 10

10,30,10 sequence of adding to shortest path is possible which increases and decreases than just non-decreases
of course, enqueue on 10, dequeue on 10 leading to enqueue of 30, and enqueue of 10

ultimately, after enqueue/dequeue finishes SPT will have 10,10,30 in non-decreasing order due to priority

maybe i should rewrite the sentence as follows:
since the priorities of the vertices added to the SPT (and in/within the SPT - *may be obvious*), are nondecreasing
I was confusing the order of distances *to be* added with the distances *already added* to the SPT.

Since ,that is out of the way, I still don't get why the statement to reassign the weight of tree vertices to 0 is needed for a general PFS implementation. I'm trying to imagine a situation in where reassign the weights/distances of already added vertices to the tree / tree vertices will help.  Bookmarks
 Posting Permissions
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement