import minPriorityQueue

d = {}  # empty dictionary

# g must be a dictionary, hashing ints to lists of ints
def numEdges(g):
    numEdges = 0
    for v in g.keys():
        numEdges += len(g[v])
    return numEdges / 2

# We do Dijkstra's algorithm (usually) on a weighted graph
wg = {'A':{'H':6, 'B':5}, 'B':{'C':5,'E':3,'A':5},\
      'C':{'G':4,'D':2,'B':5},\
      'D':{'C':2, 'F':7,'E':4},\
      'E':{'B':3, 'D':4,'F':2,'I':6,'J':9},\
      'F':{'G':9, 'D':7,'E':2},\
      'H':{'A':6, 'G':7,'I':5, 'J':8}, \
      'G':{'H':7, 'I':4, 'F':9, 'C':4},\
      'I':{'H':5, 'G':4, 'E':6, 'J':11},\
      'J':{'H':8 ,'I':11,'E':9}}


# implementation of the Floyd-Warshall All Pairs Shortest Path algorithm
def fw(wg):
    # set up the initial matrix of distances
    INFINITY = 1000000
    dis = {}
    for v in wg:
        dis[v] = {}
        for w in wg:
            dis[v][w] = INFINITY
    for v in wg:
        dis[v][v] = 0
        for w in wg[v]:
            dis[v][w] = wg[v][w]

    # Here's Floyd Warshall
    for v in wg:
        for s in wg:
            for t in wg:
                if dis[s][v] + dis[v][t] < dis[s][t]:
                    dis[s][t] = dis[s][v] + dis[v][t]
    for v in wg:
        print(v, dis[v])
                    

# implementation of Dijkstra's Algorithm
def shortestPath(wg, start, end):
    INFINITY = float('inf')   # Python trick for a very large number
    pq = minPriorityQueue.MinPriorityQueue()
    dis = {}  # holds best distances to each node so far
    parent = {} # where the shortest path to a vertex comes from

    # put all nodes in min p.q.
    for v in wg:
        dis[v] = INFINITY
        pq.insert(v, dis[v])
        
    dis[start] = 0
    parent[start] = start
    pq.decreaseKey(start, dis[start])

    while pq.notEmpty():
        # Uncomment the next line to print the distances and queue
        # print("DIS: ", dis, "\npq: ", pq.a[1:pq.heapsize], "\n")
        # Extract the lowest distance vertex, and update neighbors
        v = pq.extractMin()  # When we extract, we know the optimal distance to v
        for w in wg[v]:  # for w in the dictionary of v's neighbors
            if dis[v] + wg[v][w] < dis[w]:
                dis[w] = dis[v] + wg[v][w]
                parent[w] = v
                pq.decreaseKey(w, dis[w])

    print("The distance from ", start, " to ", end, " is ", dis[end])
    node = end
    path = end
    while parent[node] != node:
        node = parent[node]
        path = node + "->" + path
    print("The path is ", path)


print("To test, type \"shortestPath(wg, 'A', 'F')\", for example")