Bellman Ford method without require terminating after n-1 sweep and fix negative cycle loop

bellman-ford.py

from __future__ import annotations

import decimal
from typing import Union, Optional, Mapping


class Node:
    def __init__(self, name: str, connection: Optional[Mapping[Union[str, Node], Union[float, int, decimal.Decimal]]]):
        self.name = name
        self.connection: dict[str, Union[float, int, decimal.Decimal]] = \
            {
                k.name if isinstance(k, Node) else k: v # Make sure it is string
                for k, v in connection.items()
            } if connection else {}

    def __getitem__(self, name: str) -> Union[float, int, decimal.Decimal]:
        return self.connection.get(name, float('inf'))

    def copy(self) -> CalcNode:
        return CalcNode(self.name, self.connection.copy()) # Create a node for calculation so it doesn't impact itself


class CalcNode(Node):
    value: Union[float, int, decimal.Decimal]

    def __init__(self, *args, **kwargs):
        self.value = float('inf') # Default from infinite
        super().__init__(*args, **kwargs)


# node_dict: dict[str, dict[str, int]] = {
#     "A": {'B': 5, 'C': 35, 'D': 40},
#     "B": {"D":20, "E": 25},
#     "C": {"E": 30, "F": 30},
#     "D": {"F": 20},
#     "E": {"F": 25},
#     "F": {}
# }

# node_dict: dict[str, dict[str, int]] = {
#     "A": {'B': 5, 'C': 35, 'D': 40},
#     "B": {"D":20, "E": 25},
#     "C": {"E": -30, "F": 30},
#     "D": {"F": 20},
#     "E": {"F": 25},
#     "F": {}
# }

node_dict: dict[str, dict[str, int]] = {
    "A": {"B": 1},
    "B": {"C": -1},
    "C": {"D": -1},
    "D": {"E": 1, "B": -1},
    "E": {}
}

node_list = [Node(k, v) for k, v in node_dict.items()]


def calculation(initial: str, list_node: list[Node]):
    predecessor: tuple[str, dict[str, tuple[str, list[str]]]] = (initial, {})  # (initial, {end: (start, stack)})
    list_node: dict[str, CalcNode] = {node.name: node.copy() for node in list_node}
    # Check
    used = {initial, }
    for node in list_node.values():
        used = used.union(node.connection)
    if used != set(list_node):
        raise ValueError('Have unreachable node or path to non-existent node')
    for node in list_node.values():
        if node.name == initial:
            node.value = 0 # Set distance to be 0 for starting node
    modified = True
    while modified:
        checked = []
        modified = False
        current = initial
        current_node = list_node[current]
        changed = []
        while True:
            for exit, distance in current_node.connection.items():
                if current_node.value + distance < list_node[exit].value:
                    if (current, exit) not in zip(
                            predecessor[1].get(current, (current, []))[1],
                            predecessor[1].get(current, (current, []))[1][1:]
                    ):  # Create a list of tuple which display the taken paths before from stack
                        list_node[exit].value = current_node.value + distance
                        predecessor[1][exit] = (current, predecessor[1].get(current, (current, []))[1] + [current])
                        modified = True
                        changed.append(exit)  # Mark node to be impacted (Optimize path
            checked.append(current)
            if current in changed:
                changed.remove(current)
            if [name for name in changed if
                name not in checked]:  # Prioritize node that directly impacted from the change first
                current = [name for name in changed if name not in checked][0]
            else:
                if checked == list(list_node):
                    break
                current = [node_name for node_name in list_node if node_name not in checked][
                    0]  # Select the remaining node regardless (unsure if required or it could have just break
            current_node = list_node[current]
    return predecessor


result = calculation('A', node_list)
while True:
    dest = input('>')
    print(' -> '.join(result[1].get(dest, (0, []))[1] + [dest]))

Just to clarify, not having the error doesn't mean all node is reachable, this is just a simple check where they might be 2 different network that not connected to each other, hence not reachable despite an error haven't been raised