Using a heap/priority queue to represent a directed weighted graph

1
votes

I'm having trouble visualising this problem.

So I have a directed weighted graph. I need to use Dijskra's algorithm to scan this graph and print out the shortest paths. I have to use a heap/priority queue, and from my current knowledge I know these are the same thing.

However, a graph can have more than 2 children, and a heap can only have 2 children nodes. What will happen to the other children (edges) when I put this into heap format?

1
cdata-structuresheappriority-queue
I think there's a misunderstanding - you don't use the heap to represent the graph, you use it to represent the set of possible next candidates, ordered by shortest distance. The edges in the heap are completely unrelated to the edges in your graph. – happydave

1 Answers

0
votes

The representation of a heap doesn't anyway correlate itself with the graph's structure.

You are working with graph. You need to find the vertex with the minimum distance and then use it in determining the minimum distance from it. Heap is helping you to get that thing. Nothing more than that.

Here in heap, the layers doesn't represent the Graph's hierarchy, it simply related the layers of the heap with the property that any node's value will be lesser than that of it's child. That's it. It may be possible that a sibling in graph will be in parent-child relationship in heap.

You need not think that to make heap work or to make Dijkstra you need to imitate the graph structure in heap also. It's not the way to do it.(and you can't do it too).

What will happen to the other children (edges) when I put this into heap format?

  • Nothing will happen. It will work properly as long as you insert into heap with appropriate key. That's it.