2 replies to this topic

[gammaman]

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

[WingedPanther]

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.

[gammaman]

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|