3 Replies - 1205 Views - Last Post: 06 July 2013 - 01:24 PM Rate Topic: -----

#1 rozkurwiator  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 80
  • Joined: 03-July 12

Dijkstra algorithm

Posted 06 July 2013 - 08:14 AM

Hi,
I am polish student and I am going to implement dijkstra's algorithm and I can't imagine that what is going on here
decrease-key v in Q;

Could anybody explain what it means?Some easy explanation pleeease :)/>/>
algorithm is here:

http://en.wikipedia....a%27s_algorithm



Sorry that I didn't use [CODE] tags. It is copied and it would look not friendly

This post has been edited by rozkurwiator: 06 July 2013 - 08:18 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Dijkstra algorithm

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10823
  • View blog
  • Posts: 40,349
  • Joined: 27-December 08

Re: Dijkstra algorithm

Posted 06 July 2013 - 11:37 AM

It's essentially a greedy breadth-first traversal of the graph. Start at A. All of the other nodes in the graph have an unknown (infinite) cost to reach. For each of A's edges, push them into a priority queue and update the distances for the adjacent vertices. Now, pick the edge with the lowest cost from the priority queue and repeat. Do this while the Priority Queue is not empty.

I have a tutorial you may find helpful as well, albeit it is in Java.
Was This Post Helpful? 0
  • +
  • -

#3 rozkurwiator  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 80
  • Joined: 03-July 12

Re: Dijkstra algorithm

Posted 06 July 2013 - 01:22 PM

Yes I understand almost all the algorithm but what to do with that:
decrease-key v in Q; 


Yes I understand almost all the algorithm but what to do with that:
decrease-key v in Q; 


Yes I understand almost all the algorithm but what to do with that:
decrease-key v in Q; 

Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10823
  • View blog
  • Posts: 40,349
  • Joined: 27-December 08

Re: Dijkstra algorithm

Posted 06 July 2013 - 01:24 PM

Looking through the comments in the Wikipedia pseudo-code:

Quote

decrease-key v in Q; // Reorder v in the Queue


It looks like that section is associated with adding new edges to the Priority Queue.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1