Dijkstra Algorithm

Uses the principle of optimality, where every intermediary nodes belonging to the shortest path between 2 nodes are the result of the shortest path between these 2 intermediary nodes

• Negative weight => Dijkstra should not be used with arcs of negative weight. There is a possibility of get into a loop where the shortest path always goes lower in the negative values. To avoid.

// Initialize each node cost and node predecessor
foreach node in GRAPH
    node.cost = INFINITY
    node.predecessor = NIL

// source node has no predecessor...
SOURCE.predecessor = 0

// Tree of nodes near source, initially empty i.e. COMPUTED LIST OF NODES...
COMPUTED_CONTAINER = {}

// Queue with all the nodes of the graph initially  i.e. UNCOMPUTED LIST OF NODES...
NODES_QUEUE =  GRAPH.nodes.all

for NODES_QUEUE.times
    // set current node to node with lowest cost in the NODES_QUEUE, starts with source node...
    current_node = NODES_QUEUE.min()
    
    // Remove current node from queue
    NODES_QUEUE.remove(current_node)
    
    // Add current_node to computed container
    COMPUTED_CONTAINER.append(current_node)

    // Loop through all nodes adjacent to current_node in queue
    for adjacent_node in NODES_QUEUE.adjacentTo(current_node)

        // Calculate temporary value of the node
        temp = current_node.cost + arc(current_node, adjacent_node).weight

        // If new value is less than the one before on the adjacent node
        if temp < adjacent_node.cost
            
            // Update to the new lower cost
            adjacent_node.cost = temp

            // OPTIONAL: Set the predecessor to this adjacent node to the current node
            // as it is the new shortest path to this node. Useful to find the actual path
            adjacent_node.predecessor = current_node

Multiple Implementations

• Adjacency Valued Matrix and random Queue in terms of node cost => execution time in complexity O(n2)
• Minimal Heap as Queue of nodes and arcs represented in an adjacency list => execution time in complexity O(mLog(n))