•

Check out our Community Blogs

Register and join over 40,000 other developers!

### Recent Blog Entries

• phi

I love this community !

# priority queue heap.

shortest path

2 replies to this topic

### #1 gammaman

gammaman

CC Resident

• Just Joined
• 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
• 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