Demonstration of Dijkstra's algorithm

dijkstra.py

# -*- coding: utf-8 -*-
"""
Created on Wed Apr 10 01:05:05 2024

@author: alankar
"""
from typing import List, Optional, Union

_large_distance = 10000
          
class node:
    def __init__(self) -> None:
        self.neigh_nodes = []
        self.current_distance: Union[int, float] = _large_distance
        self.prev_node: Optional = None
    
    def make_connections(self, this_node_name: List[str], 
                         to_node_names: List[str], 
                         distances: Union[List[int], List[float]]) -> None:
        self.name = this_node_name
        self.to_neigh_distances  = distances
        self.neigh_names = to_node_names
    
    def setup_graph(self, all_nodes: List["node"]) -> None:
        for neigh_name in self.neigh_names:
            for node in all_nodes:
                if node.name == neigh_name:
                    self.neigh_nodes.append(node)

def give_node_from_name(node_name: str, 
                        all_nodes: List["node"]) -> Optional[node]:
    for node in all_nodes:
        try:
            if node.name == node_name:
                return node
        except AttributeError:
            print("Error: Build node connections first!")
            return None
    print("Error: Name does not match any existing node!")


if __name__ == "__main__":
    example = 2
    tot_nodes = 6 if example==1 else 7
    nodes = [node() for i in range(tot_nodes)]
    
    # setup
    if example==1:
        nodes[0].make_connections('A', ['B', 'D'], [2, 8]) 
        nodes[1].make_connections('B', ['A', 'D', 'E'], [2, 5, 6]) 
        nodes[2].make_connections('C', ['E', 'F'], [9, 3]) 
        nodes[3].make_connections('D', ['A', 'B', 'E', 'F'], [8, 5, 3, 2])
        nodes[4].make_connections('E', ['B', 'C', 'D', 'F'], [6, 9, 3, 1])
        nodes[5].make_connections('F', ['C', 'D', 'E'], [3, 2, 1])
    else:
        nodes[0].make_connections('A', ['C', 'F'], [3, 2]) 
        nodes[1].make_connections('B', ['D', 'E', 'F', 'G'], [1, 2, 6, 2]) 
        nodes[2].make_connections('C', ['A', 'D', 'E', 'F'], [3, 4, 1, 2]) 
        nodes[3].make_connections('D', ['B', 'C'], [1, 4])
        nodes[4].make_connections('E', ['B', 'C', 'F'], [2, 1, 3])
        nodes[5].make_connections('F', ['A', 'B', 'C', 'E', 'G'], [2, 6, 2, 3, 5])
        nodes[6].make_connections('G', ['B', 'F'], [2, 5])
        
    for node in nodes:
        node.setup_graph(nodes)
    
    start_node = give_node_from_name('A', nodes)
    start_node.current_distance = 0
    current_node = start_node
    explored_node_count = 0
    explored_node_names = []
    
    while (explored_node_count<=tot_nodes):
        for indx, neigh_node in enumerate(current_node.neigh_nodes):
            if neigh_node.name in explored_node_names: 
                continue
            distance = current_node.current_distance + current_node.to_neigh_distances[indx]
            if (distance < neigh_node.current_distance):
                neigh_node.current_distance = distance
                neigh_node.prev_node = current_node
        shortest_distance = _large_distance
        select = 0
        explored_node_names.append(current_node.name)
        for indx, neigh_node in enumerate(current_node.neigh_nodes):
            if neigh_node.name in explored_node_names: 
                continue
            if neigh_node.current_distance < shortest_distance:
                select = indx
                shortest_distance = neigh_node.current_distance
        current_node = current_node.neigh_nodes[select]
        explored_node_count += 1
        
    dest_node_name = 'C' if example==1 else 'B'
    route = [dest_node_name,]
    
    for node in nodes:
        if node.name == dest_node_name:
            dest_node = node
    
    current_node = dest_node
    while (current_node != start_node):
        route.append(current_node.prev_node.name)
        current_node = current_node.prev_node
    
    for indx, node_halt in enumerate(route[::-1]):
        if indx != (len(route)-1):
            print(node_halt, "-->", end=" ")
        else:
            print(node_halt)
    print("Distance:", dest_node.current_distance)