Custom implementation of the djikstras algorithm.

djikstras.py

import math
from pprint import pprint as pp

class Node:
    name = ""
    def __init__(self, name=None):
        self.name = name
    
    def __repr__(self) -> str:
        return f"<Node: {self.name}>"

class Vertice:
    nodes: list[Node] = []
    weight: float = 0.0

    def __init__(self, node1: Node, node2: Node, weight: float):
        self.nodes = [node1, node2]
        self.weight = weight
    
    def __repr__(self) -> str:
        return f"<Vertice: nodes-{self.nodes}, weight-{self.weight}>"


class Graph:
    nodes: set
    vertices: list[Vertice] = []

    def __init__(self, nodes=[], vertices=[]) -> None:
        self.nodes = nodes
        self.vertices = vertices
    
    def get_shortest_path(self, node: Node):
        details: list[dict] = []
        visited_nodes = []
        unvisited_nodes = self.nodes.copy()
        
        current_node = node
        current_node_weight = 0

        for n in self.nodes:
            if n == node:
                details.append({"node": n, "weight": 0.0, "previous-node": None })
            else:
                details.append({"node": n, "weight": math.inf, "previous-node": None})
        unvisited_nodes.remove(node)

        while set(self.nodes) != set(visited_nodes):
            neighbors_paths = self.get_node_vertices(current_node)
            

            for path in neighbors_paths:
                neighbour = self.get_immediate_neighbor(path, current_node)
                weight = path.weight

                for x in details:
                    if (x["node"] == neighbour) and (weight + current_node_weight < x["weight"]):
                        x["weight"] = weight + current_node_weight
                        x["previous-node"] = current_node
            
            visited_nodes.append(current_node)
            new_node_details = self.get_lowest_value_unvisited_node(details, visited_nodes)
            current_node = new_node_details["node"]
            current_node_weight = new_node_details["weight"]

        return details
    
    def get_lowest_value_unvisited_node(self, details: list[dict], visited_nodes: list[Node]):
        lowest_value_node = None
        lowest_value = math.inf
        for detail in details:
            if detail["node"] in visited_nodes:
                continue

            if detail["weight"] < lowest_value:
                lowest_value_node = detail["node"]
                lowest_value = detail["weight"]
                
        return { "node": lowest_value_node, "weight": lowest_value }

    def get_node_vertices(self, node: Node) -> list[Vertice]:
        node_vertices = []
        for vertice in self.vertices:
            if node in vertice.nodes:
                node_vertices.append(vertice)
        return node_vertices
    
    def get_immediate_neighbor(self, vertice: Vertice, node: Node):
        for n in vertice.nodes:
            if n != node:
                return n
        return None

def run():
    node_a = Node("a")
    node_b = Node("b")
    node_c = Node("c")
    node_d = Node("d")
    node_e = Node("e")

    vertice_a_b = Vertice(node_a, node_b, 6)
    vertice_a_d = Vertice(node_a, node_d, 1)
    vertice_d_b = Vertice(node_d, node_b, 2)
    vertice_d_e = Vertice(node_d, node_e, 1)
    vertice_b_e = Vertice(node_b, node_e, 2)
    vertice_e_c = Vertice(node_e, node_c, 5)
    vertice_b_c = Vertice(node_b, node_c, 5)

    nodes = [
        node_a,
        node_b,
        node_c,
        node_d,
        node_e,
    ]

    vertices = [
        vertice_a_b,
        vertice_a_d,
        vertice_d_b,
        vertice_d_e,
        vertice_b_e,
        vertice_e_c,
        vertice_b_c,
    ]

    graph = Graph(nodes, vertices)
    shortest_paths = graph.get_shortest_path(node_a)
    pp(shortest_paths)

if __name__ == "__main__":
    run()