A python implementation of Dijkstra's Algorithm

Dijkstra.py

"""
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
USAGE:
use this file like a module (aka. create an init.py file at the directory you want to use it at and "import Dijkstra" in your code)

to create a node/ or a point:
variable = Dijkstra.Node('variableName', {'otherVariableName': distance,...}

and to create a graph/ table of nodes/ points:
tableOfPoints = Dijkstra.Graph([variable1, variable2, variable3, variable4])

and to return the shortest distance from a node/ point:
distanceMap = Dijkstra.dijkstra(tableOfPoints, 'variableName') # where variableName is the name of the variable you're taking distances from.
distanceMap['variableName2']['distance'] # where variableName2 is the node you want to go to will be the distance.


so for example: (the same example that proceeds when you attempt to run this file)

A = Node('A', {'B': 10, 'C': 5})
B = Node('B', {'A': 10, 'D': 7})
C = Node('C', {'A': 5, 'D': 11})
D = Node('D', {'C': 11, 'B': 7})
exampleGraph = Graph([A, B, C, D])
s = dijkstra(exampleGraph, 'A')
print(s) # Prints a dictionary of distances and more
print(s['D']['distance']) # Prints an integer distance from A to D
and if you were interested in the route s['D']['lastNode'] gives you the node it came from.
"""

class Node:  # A point on a graph, keeps track of connected points with weight.
    def __init__(self, name, connections):
        self.name = name
        self.connections = connections

    def connect(self, node):
        return self.connections.get(node, False)


class Graph:  # A graph that contains points as a list, separated so that depictions can be implemented as methods
    def __init__(self, nodes):
        self.nodes = nodes


def dijkstra(graph, start):  # Implementation of Dijkstra's Algorithm
    nodes = {x.name: {'node': x, 'lastNode': 'unknown', 'distance': float('Inf'), 'visited': False} for x in graph.nodes}
    nodes[start]['distance'] = 0
    nodes[start]['lastNode'] = None
    everything_visited = False
    while not everything_visited:  # This is where the magic happens
        unvisited = [nodes[node] for node in nodes.keys() if not nodes[node]['visited']]
        this = min(unvisited, key=lambda x: x['distance'])
        for node in unvisited:
            name = node['node'].name
            distance = node['node'].connect(this['node'].name)
            if distance:
                curr = nodes[name]['distance']
                new = distance + this['distance']
                if curr > new:
                    nodes[name]['distance'] = new
                    nodes[name]['lastNode'] = this['node'].name
        this['visited'] = True
        if len(unvisited) == 1:  # This condition ensures we were just getting through the last unvisited node
            everything_visited = True
    return nodes


"""
The nodes dictionary is 2 dimensional:
nodes[x][y] where x and y are keys

x is the name of the node/ point which is obtained from node.name
y is one of <'node', 'lastNode', 'distance', 'visited'> with types <node, str, int, bool> respectively.
it would be more memory efficient to make y be the index of a list, but when it's a dictionary it's more readable.

¬ Look below for example usage ¬
"""


if __name__ == 'main':
    A = Node('A', {'B': 10, 'C': 5})
    B = Node('B', {'A': 10, 'D': 7})
    C = Node('C', {'A': 5, 'D': 11})
    D = Node('D', {'C': 11, 'B': 7})
    exampleGraph = Graph([A, B, C, D])
    s = dijkstra(exampleGraph, 'A')
    print(s)
    print(s['D']['distance'])