Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

priority queue heap.

shortest path

  • Please log in to reply
2 replies to this topic

#1 gammaman

gammaman

    CC Resident

  • Just Joined
  • PipPipPipPip
  • 70 posts

Posted 23 March 2009 - 08:35 AM

Below are the solved steps from a digraph for dijkstra. What would the priority queue heap (as an array) be.

From step 1 the shortest path is 1 from node 4
From step 2 the shortest path is 2 from node 2
From step 3 the shortest paths are 3 from node 3 and 3 from node 5
From step 4 the shortest path is 5 from node 7
From step 5 the shortest path is 6 from node 6
  • 0

#2 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 23 March 2009 - 09:04 AM

Moved to the correct forum.

You will have to provide a little more information. I don't know that there is a standard way to encode that data into a priority queue heap. Also, this looks suspiciously like homework, which raises the question of what you think the answer might be.
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#3 gammaman

gammaman

    CC Resident

  • Just Joined
  • PipPipPipPip
  • 70 posts

Posted 23 March 2009 - 09:23 AM

Well, it was homework, but I think I did the hardest part. I already applied dijkstra to a digraph and came up with the results I posted. For each step I am also supposed to show a priority queue. My prof did not specify how to represent the queue. I figured a heap would be easier than a binary tree. So if I had to guess, it would be.
____________
|1|2|3|3|5|6|
  • 0





Also tagged with one or more of these keywords: shortest path

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download