inf = float('Inf') #for "no edge" (why not just 0?)

def dijkstra(G, s):
    """ Find shortest paths from source to all other nodes in G.
        G is a weighted, directed Graph represented as a matrix.
        Missing edges are assigned weight = float('Inf').
        Return list of distances and list of previous nodes """
    n = len(G) #number of rows in matrix = number of nodes

    #Initialization
    dist = [inf]*n
    dist[s] = 0
    prev = [-1]*n
    prev[s] = s

    Q = [s] #list of nodes currently "in the game"

    #Main loop of the algorithm 
    while len(Q) != 0:  #while more nodes to handle
        #print("Q = ", Q)
        u = find_min_dist(Q, dist) #get node from Q with minimal distance from source
        Q.remove(u)                #u is "out of game"

        for v in range(n): #go over all neighbors v of u
            if dist[v] > dist[u] + G[u][v]: #found a shorter way to v
                dist[v] = dist[u] + G[u][v] #update v's dist
                prev[v] = u                 #u is now v's prev
                if v not in Q:              #a new node discovered?
                    Q += [v]                #v "enters the game"
        #print("---")

    #Termination, Q is empty
    return dist, prev

def find_min_dist(Q, dist):
    ''' Return the node in the list Q with minimal dist.
        Assumes Q is not empty '''
    mini = Q[0]
    for v in Q:
        if dist[v] < dist[mini]:
            mini = v
    return mini

def shortest_path(prevs, source, target):
    ''' Return the shortest path in G from source to target.
        Uses Dijkstra's algorithm.
        G is a weighted, directed Graph represented as a matrix.
        The output is a list of the nodes in the path '''

    if prevs[target] == -1:  #no path exists from source to target
        return []
    path = [target]
    v = target
    while v != source:
        v = prevs[v]         #previous node in the path
        path = [v] + path   #append from left
    return path

#the example graph from the presentations
G = [ [inf,   2, inf, inf, inf, inf, inf],
       [inf, inf,   2,   1, inf, inf, inf],
       [inf, inf, inf,   1, inf,   2, inf],
       [  5, inf, inf, inf,   1,   6,   5],
       [  1, inf, inf, inf, inf, inf, inf],
       [inf, inf, inf, inf, inf, inf,  10],
       [inf, inf, inf, inf,   3, inf, inf],    ]


#other graphs
G1 = [\
        [0.0,  1.0,  3.0,  inf],
        [1.0,  0.0,  1.0,  4.0],
        [3.0,  1.0,  0.0,  2.0],
        [inf,  4.0,  2.0,  0.0]]

G2 = [ [inf,3,1],[inf,inf,inf],[inf,1,inf] ]

G3 = [ [inf,10,5,inf],
       [inf,inf,3,inf],
       [inf,4,inf,1],
       [inf,2,inf,inf]]



source = 1
dists, prevs = dijkstra(G, source)
##print(dists)
##print(prevs)
##
##print("shortest_path(prevs,source,0))
##
##G[4][0] = inf
##dists, prevs = dijkstra(G, source)
##print(shortest_path(prevs,source,0))