Notices
Results 1 to 5 of 5

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

  1. #1 Dijkstra's Algorithm(Priority- First Search) 
    New Member
    Join Date
    Jul 2011
    Posts
    3
    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 ?


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Freshman
    Join Date
    Oct 2010
    Posts
    98
    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).


    Reply With Quote  
     

  4. #3  
    New Member
    Join Date
    Jul 2011
    Posts
    3
    Quote Originally Posted by BlasW View Post
    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
    Reply With Quote  
     

  5. #4  
    Forum Freshman
    Join Date
    Oct 2010
    Posts
    98
    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.
    Last edited by BlasW; July 26th, 2011 at 09:16 AM.
    Reply With Quote  
     

  6. #5  
    New Member
    Join Date
    Jul 2011
    Posts
    3
    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.
    Reply With Quote  
     

Bookmarks
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
  •