graph

import math

class Graph:
    def __init__(self):
        self.edges = []
        self.nodes = []

    def add_edge(self, key1, key2, w):
        for node in self.nodes:
            if node.key == key1:
                n1 = node
            elif node.key == key2:
                n2 = node
        n1.adj.append(Edge(n2, w))
        n2.adj.append(Edge(n1, w))
        n1.adj.sort(key=lambda e: e.w)
        n2.adj.sort(key=lambda e: e.w)

    def add_node(self, key):
        self.nodes.append(Node(key))

    def find_shortest_dist(self, key1, key2):
        for node in self.nodes:
            node.visited = False
            node.dist = math.inf
            if node.key == key1:
                n1 = node
            elif node.key == key2:
                n2 = node

        n1.dist = 0
        self._traverse(n1)
        return n2.dist


    def find_shortest_path(self, key1, key2):
        for node in self.nodes:
            node.parent = None
            node.visited = False
            node.dist = math.inf
            if node.key == key1:
                n1 = node
            elif node.key == key2:
                n2 = node

        n1.dist = 0
        self._traverse(n1, n2)
        return n2

    def print_shortest_path(self, key1, key2):
        node = self.find_shortest_path(key1, key2)
        self._print_path(node)
        print("DONE")

    def _print_path(self, node):
        if node.parent is not None:
            self._print_path(node.parent)
        print(node.key, end=" --> ")
            
    def _traverse(self, node, target):
        solved = []
        for n in self.nodes:
            n.dist = math.inf
        node.dist = 0

        while target not in solved:
            cnode = min(self.nodes, key=lambda n: (n in solved, n.dist))

            for e in cnode.adj:
                if e.n not in solved:
                    if cnode.dist + e.w < e.n.dist:
                        e.n.dist = cnode.dist + e.w
                        e.n.parent = cnode

            solved.append(cnode)
            

class Edge:
    def __init__(self, n, w):
        self.n = n
        self.w = w

class Node:
    def __init__(self, key):
        self.key = key
        self.adj = []
        self.dist = math.inf
        self.visited = False
        self.parent = None

    def __repr__(self):
        return f"Node(key={self.key}, dist={self.dist})"

g = Graph()
for i in range(9):
    g.add_node(i)

g.add_edge(0, 1, 4)
g.add_edge(1, 2, 8)
g.add_edge(2, 3, 7)
g.add_edge(3, 4, 9)
g.add_edge(4, 5, 10)
g.add_edge(5, 6, 2)
g.add_edge(6, 7, 1)
g.add_edge(7, 8, 7)
g.add_edge(7, 0, 8)
g.add_edge(1, 7, 11)
g.add_edge(6, 8, 6)
g.add_edge(2, 8, 2)
g.add_edge(2, 5, 4)
g.add_edge(3, 5, 14)

g.print_shortest_path(0, 8)