Python Implementation of Dijkstra with python heapq (priority Queue)

dijkstra.py

# Dijkstra Algo with no destination.
# Calculate -> Shortest path from start to all nodes

import math
import heapq
from typing import Dict, List, Tuple

# Maintains neighbours and weights
graph: Dict[int, List[Tuple[int, int]]] = dict()

# Maintains known distance to vertices
distance: Dict[int, int] = dict()


def init_graph(vertices, edges):
    global distance
    global graph

    for vertex in vertices:
        distance[vertex] = math.inf
        graph[vertex] = list()

    for edge in edges:
        u, v, w = edge  # edge = (start, end, weight)
        graph[u].append((w, v))


def dijkstra(start, vertices, edges):
    global graph
    global distance

    init_graph(vertices, edges)
    priority_q = []

    heapq.heappush(priority_q, (0, start))
    distance[start] = 0

    while priority_q:
        current_dist, u = heapq.heappop(priority_q)

        for edge in graph[u]:
            w, v = edge
            new_distance = current_dist + w

            if new_distance < distance[v]:
                distance[v] = new_distance
                heapq.heappush(priority_q, (distance[v], v))


if __name__ == '__main__':
    source = "A"

    dijkstra(
        start=source,
        vertices=["A", "B", "C"],
        edges=[("A", "B", 1), ("B", "C", 1), ("A", "C", 5)]
    )

    print(f"Source -> {source}")

    for v, dist in distance.items():
        print(f"{source} --> {v} : {dist}")

    print(f"Finished")