import math import collections from heapq import * class Node: def __init__(self, id): self.id = id self.edges = [] def add_route(self, to, cost): self.edges.append({ "to": to, "cost": cost }) def __lt__(self, t): return True def dijkstra(nodes): start = nodes[0] end = nodes[-1] distance_from_start = {n: math.inf for n in nodes} distance_from_start[start] = 0 minHeap = [] heappush(minHeap, (0, start)) while minHeap: (distance, current) = heappop(minHeap) if distance_from_start[current] < distance: continue for edge in current.edges: cost = edge["cost"] to = edge["to"] if cost + distance_from_start[current] < distance_from_start[to]: distance_from_start[to] = cost + distance_from_start[current] heappush(minHeap, (cost + distance_from_start[current], to)) return distance_from_start[end] def add_node(f, to, weight): f.add_route(to, weight) def main(): node1 = Node(1) node2 = Node(2) node3 = Node(3) node4 = Node(4) node5 = Node(5) node6 = Node(6) node7 = Node(7) add_node(node1, node2, 10) add_node(node1, node3, 16) add_node(node1, node4, 12) add_node(node2, node3, 18) add_node(node2, node5, 4) add_node(node4, node3, 3) add_node(node3, node6, 1) add_node(node6, node7, 9) add_node(node5, node7, 21) dist = dijkstra([node1, node2, node3, node4, node5, node6, node7]) print(dist) main()