Priority queue/min heap for directed graph with Dijkstra's alg

Question

For an assignment I need to implement Dijkstra's algorithm using a priority queue implemented as a min heap. I already have an implementation in which I use a distance table and an unordered array of the unprocessed vertexes. (As described towards the bottom of the page here).

An example input file is given below, where the first line is the number of vertexes and each line after is: source, destination, weight.

3
1 2 3
3 2 1
1 3 1

My initial thought was to treat each edge in the graph as a node in the heap, but that isn't right because one of the test files has 15677372 edges and I can't even make an array that big without an immediate segfault. After implementing the method with the array of unprocessed vertexes it seems that I need to somehow replace that array with the heap, but I'm not sure how to go about that.

Could anyone point me in the right direction?

Answer 1

Typically, in Dijkstra's algorithm, your priority queue will hold the nodes in the graph and the best estimated distance to that node so far. The standard technique is to enqueue all nodes in the graph into the priority queue initially at distance ∞, then to use the queue's decrease-key operation to lower them as needed.

This is often completely infeasible from a memory standpoint, so an alternate interpretation is to keep the queue empty initially and then seed it with the start node at distance 0. Every time you process a node, you then update the distance estimate for each of its adjacent nodes. You do this as follows:

• If the node is already in the priority queue, you can use decrease-key to lower the node's distance.
• If the node is not already in the priority queue, then you insert it at the required priority.

This keeps the priority queue small for graphs that aren't absurdly dense.

Hope this helps!