dijkstra.py

import collections

""" TEST GRAPH
graph = {
        'A': {'A': -1, 'B': 2, 'C': 3, 'D': -1, 'E': -1, 'F': -1, 'G': -1, 'H': -1},
         'B': {'A': 2, 'B': -1, 'C': -1, 'D': 4, 'E': -1, 'F': -1, 'G': -1, 'H': -1},
         'C': {'A': 3, 'B': -1, 'C': -1, 'D': -1, 'E': 4, 'F': 5, 'G': -1, 'H': -1},
         'D': {'A': -1, 'B': 4, 'C': -1, 'D': -1, 'E': -1, 'F': -1, 'G': 3, 'H': -1},
         'E': {'A': -1, 'B': -1, 'C': 4, 'D': -1, 'E': -1, 'F': -1, 'G': -1, 'H': 5},
         'F': {'A': -1, 'B': -1, 'C': 5, 'D': -1, 'E': -1, 'F': -1, 'G': 2, 'H': 3},
         'G': {'A': -1, 'B': -1, 'C': -1, 'D': 3, 'E': -1, 'F': 2, 'G': -1, 'H': -1},
         'H': {'A': -1, 'B': -1, 'C': -1, 'D': -1, 'E': 5, 'F': 3, 'G': -1, 'H': -1}
         }
"""

with open('matrixB.txt', 'r') as f:
    columns = next(f).split()
    matrix = collections.defaultdict(dict)
    for line in f:
        items = line.split()
        row, vals = items[0], items[1:]
        for col, val in zip(columns, vals):
            matrix[col][row] = int(val)
print(matrix)

def dijkstra(graph,start,end):
    D = {}
    P = {}

    for node in graph.keys():
        D[node] = -1
        P[node] = ""

    D[start] = 0
    unseenNodes = list(graph.keys())

    while len(unseenNodes) > 0:
        shortest = None
        node = ''
        for tempNode in unseenNodes:
            if shortest == None:
                shortest = D[tempNode]
                node = tempNode
            elif D[tempNode] < shortest:
                shortest = D[tempNode]
                node = tempNode

        unseenNodes.remove(node)

        for childNode, childValue in graph[node].items():
            if D[childNode] < D[node] + childValue:
                D[childNode] = D[node] + childValue
                P[childNode] = node

    path = []

    node = end
    while not (node == start):
        if path.count(node) == 0:
            path.insert(0,node)
            node = P[node]
        else:
            break

    path.insert(0,start)
    return path

start = input("Start: ")
end = input("End: ")
path=dijkstra(matrix, start, end)
print("The shortest path from "+start+" to "+end+" is: ",path)