This Python program processes a graph with postive edge weights using Dijkstra's algorithm, to find the minimum total weight from a starting node to a destination node. A priority queue, specifically a minimum binary heap, determines the next node to process in the graph. The node key in the heap is the same as the weight of a node in the graph.
The heap is made up of all unfixed nodes. The heap maintains the lowest weight node at the top of the heap. All nodes in the graph start as unfixed nodes. The starting node in the graph is given a weight of 0, and all other nodes a weight of infinity. To determine the next node in to graph to be processed, the lowest weighted node is removed from the top of the heap. A node is processed as follows. In the graph, the weight of the lowest weighted unprocessed node becomes fixed; the unfixed node becomes a fixed node. All outgoing edges from the lowest weighted node are relaxed to update the weights of nodes on the other ends of the outgoing edges. When edges are relaxed, the following two weights are summed: the weight of the just fixed node and the weight of the edge that leads to the node with the updated weight. If edge relaxation results in lowering the weight of a node, the node with a lowered weight is re-entered into the heap.
As nodes are re-entered into the heap with lower weights, the heap will contain multiple instances of the same node but with different weights. For example, a particular node with a high weight is entered into the heap. Later, edge relaxation results in the particular node having a low weight. The particular node is re-entered into the heap with a low weight. As a result, the heap contains multiple instances of the particular node - one with a high weight and one with a low weight. To prevent any node from being processed multiple times, an array of boolean flags keeps track of whether any node has been processed yet. The first time a particular node - with a low weight - is popped from the heap, the corresponding flag in the array of flags is changed to true, and the particular node is processed in the graph. On subsequent occasions when the particular node - with a high weight - is popped from the heap, the corresponding flag in the array of flags is already true, so the particular node is not processed in the graph.
One potential source of bugs is the storage of weights in the heap. When a node is stored in the heap, the weight of the node should be stored by value. Or if not by value, at least not by reference if the same weight is updated when edges are relaxed in the graph. If not, then when edge relaxation in the graph changes node weights, then the node weights in the heap will change. Such a heap will no longer be a priority queue, and will not work.