Coding Test

dijkstra.py

import heapq
import sys

INF = float('inf')  # or sys.maxsize

def dijkstra(start: int, graph: list) -> list:
    queue = []
    heapq.heappush(queue, (0, start))
    shortest_distances = [INF] * len(graph)
    shortest_distances[start] = 0
    
    while queue:
        distance, node = heapq.heappop(queue)
        
        if shortest_distances[node] < distance:
            continue
        
        for adjacent_distance, adjacent_node in graph[node]:
            new_distance = distance + adjacent_distance
            if new_distance < shortest_distances[adjacent_node]:
                shortest_distances[adjacent_node] = new_distance
                heapq.heappush(queue, (new_distance, adjacent_node))
        
    return shortest_distances