Dijkstra algorithm

dijkstra.py

import heapq

def dijkstra (n, s, map, cost):
    
    cost = dict()
    Q = list()      # the priority queue
    P = dict()      # P[i] = 1, if node i has been removed from the heap before
    init_adj()

    for i in range(1, n + 1):
        cost[i] = float('inf')
        P[i] = 0
    
    cost[s] = 0
    heapq.heappush(Q, (cost[s], s))

    while Q:
        # Each pop operation takes O(log E) and there are O(E) operations in total. 
        top = heappop(Q)
        if P[top] == 0:
            P[top] = 1
        else:
            # skip edge relaxation, if the node has been removed from the queue before
            continue
        index = top[1]

        for i in range(1, n + 1):
            weight = map[index][i]
            if cost[i] > (cost[index] + weight):
                cost[i] = cost[index] + weight
                # Every edge in the graph has at most one change to insert a node 
                # into the queue in edge relaxation. So there are O(E) possible insertions 
                # and the size of the queue is O(E). Each insertion takes O(log E). 
                heapq.heappush(Q, (cost[i], i))

    return cost


    """
    C++ VERSION

    short i;
    typedef pair<short,short> node;
    set<node> Q;
    set<node>::iterator p;
    
    init_adj();
    for(i=1;i<=n;i++)
        cost[i]=M;
    cost[s]=0;
    
    Q.insert(node(0,s));
    while(Q.empty()==false){
        node top=*Q.begin();
        Q.erase(Q.begin());
        int index=top.second;
        
        for(i=1;i<=n;i++){
            int weight=map[index][i];
            if(cost[i]>cost[index]+weight){
                if(cost[i]!=M)
                    Q.erase(Q.find(node(cost[i],i)));
                cost[i]=cost[index]+weight;
                Q.insert(node(cost[i],i));
            }
        }
    }

    """