INFINITE = 99999999999


# Noel -> Robbe: 1 cent
# Noel -> Seppe: 1 cent

Graph = {'Alice': {'R2':2},
         'R2': {'Alice': 2, 'R5':6, 'R6':2, 'R7':6},
         'R3': {'R7':5,'R5':10,'R4':1},
         'R4':{'Bob': 8, 'R3':1, 'R5': 1, 'R6':4},
         'R5':{'R2':6,'R7':9,'R3':10,'R4':1},
         'R6':{'R2':2,'R4':4},
         'R7':{'R2':6,'R3':5,'R5':9},
         'Bob':{'R4':8}}


# Object example:
# {
#   id: 'R2',
#   length: 5,
#   done: False,
#   path: {'Alice', 'R1'}
# }

priorityQueue = []

def sortPriorityQueue(pq):
    pq.sort(key=lambda x: x['length'], reverse=False)
    return pq

def getIndexOfRelayInPQ(pq, id):
    for i in range(len(pq)):
        if pq[i]['id'] == id:
            return i
    return -1

def getIndexOfFirstNonDone(pq):
    for i in range(len(pq)):
        if pq[i]['done'] == False:
            return i
    return -1

def getNonDoneCount(pq):
    result = 0
    for i in range(len(pq)):
        if pq[i]['done'] == False:
            result += 1
    return result

def dijkstra(graph, startNode, endNode):
    global priorityQueue

    # Put all relays in PQ, and set length 0 for starting point
    priorityQueue = []
    for relay in graph:
        priorityQueue.append({
            'id': relay,
            'length': 0 if (relay == startNode) else INFINITE,
            'done': False,
            'path': []
        })

    while getNonDoneCount(priorityQueue) > 0:
        shortestIndex = getIndexOfFirstNonDone(priorityQueue)
        shortest = priorityQueue[shortestIndex]

        print('Doing ' + str(shortest['id'] + ': '))

        if(shortest['id'] == endNode):
            return

        for neighbour in Graph[shortest['id']]:
            lengthToNeighbour = shortest['length'] + Graph[shortest['id']][neighbour]
            indexOfNeighbour = getIndexOfRelayInPQ(priorityQueue, neighbour)
            print('\tUpdating ' + str(priorityQueue[indexOfNeighbour]['id']))
            if lengthToNeighbour < priorityQueue[indexOfNeighbour]['length']:
                print('\tUpdating length to ' + str(lengthToNeighbour))
                priorityQueue[indexOfNeighbour]['length'] = lengthToNeighbour
                priorityQueue[indexOfNeighbour]['path'] = shortest['path'][:]
                priorityQueue[indexOfNeighbour]['path'].append(shortest['id'])
        priorityQueue[getIndexOfFirstNonDone(priorityQueue)]['done'] = True

        priorityQueue = sortPriorityQueue(priorityQueue)

dijkstra(Graph, 'Alice', 'Bob')

# Printing result
print('####################################################')
bobIndex = getIndexOfRelayInPQ(priorityQueue, 'Bob')
print('Shortest path from Alice to Bob: ')
print('\tLength: ' + str(priorityQueue[bobIndex]['length']))
print('\tPath: ' + str(priorityQueue[bobIndex]['path']))
print('####################################################')