import heapq

def dijkstra_verbose(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    step = 0

    print(f"\n--- Dijkstra's Algorithm from Node {start} ---\n")
    print(f"Initial distances: {distances}")

    while pq:
        current_distance, current_node = heapq.heappop(pq)
        print(f"\nStep {step}: Visiting node {current_node} with current distance {current_distance}")

        if current_distance > distances[current_node]:
            print("\tSkipping since a shorter path is already found.")
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                old_distance = distances[neighbor]
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
                print(f"\tUpdating distance to node {neighbor}: {old_distance} -> {distance}")
            else:
                print(f"\tNo update required for node {neighbor} (current: {distances[neighbor]}, new: {distance})")

        print(f"Distances after step {step}: {distances}")
        step += 1

    print(f"\nFinal shortest distances from node {start}: {distances}")
    return distances

# Compute SSSPT for each node and print the steps
graph = {
    0: {1: 3, 2: 1},
    1: {3: 2},
    2: {1: 1, 4: 5, 5: 5},
    3: {2: 4, 4: 3},
    4: {5: 1, 6: 3},
    5: {6: 1, 7: 4},
    6: {7: 1},
    7: {}
}

#Compute SSSPT for each node and print the steps
#for node in graph:
#    dijkstra_verbose(graph, node)

# Compute SSSPT for a specific node and print the steps
dijkstra_verbose(graph, 0)