algo-dijkstra-shortest-path

Answer

Here is a complete Python implementation of Dijkstra's shortest-path algorithm using a min-heap priority queue, with negative edge detection:

import heapq

def dijkstra_shortest_path(graph, source):
    """
    Dijkstra's algorithm using min-heap priority queue.

    Args:
        graph: dict mapping node -> list of (neighbor, weight)
        source: starting node

    Returns:
        (distances, predecessors, negative_edge_detected)
        - distances: dict of shortest distances from source to each node
        - predecessors: dict for path reconstruction
        - negative_edge_detected: bool
    """
    # Step 1: Check for negative edges
    for u in graph:
        for v, w in graph[u]:
            if w < 0:
                return None, None, True  # Negative edge detected

    # Step 2: Initialize distances and predecessors
    distances = {node: float('inf') for node in graph}
    distances[source] = 0
    predecessors = {node: None for node in graph}

    # Step 3: Min-heap priority queue: (distance, node)
    pq = [(0, source)]
    visited = set()

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

        # Skip if we already found a better path
        if current_dist > distances[u]:
            continue

        # Process neighbors
        for v, weight in graph.get(u, []):
            new_dist = current_dist + weight
            if new_dist < distances[v]:
                distances[v] = new_dist
                predecessors[v] = u
                heapq.heappush(pq, (new_dist, v))

    return distances, predecessors, False


def reconstruct_path(predecessors, target):
    """Reconstruct the shortest path from source to target using predecessors."""
    path = []
    node = target
    while node is not None:
        path.append(node)
        node = predecessors.get(node)
    return list(reversed(path))


# ----- Example usage -----
if __name__ == "__main__":
    # Example: simple directed weighted graph
    example_graph = {
        'A': [('B', 4), ('C', 2)],
        'B': [('C', 3), ('D', 2), ('E', 3)],
        'C': [('B', 1), ('D', 4)],
        'D': [('E', 1)],
        'E': []
    }

    dist, pred, neg = dijkstra_shortest_path(example_graph, 'A')
    if neg:
        print("Negative edge detected! Use Bellman-Ford instead.")
    else:
        print("Shortest distances from A:", dist)
        print("Path A->E:", reconstruct_path(pred, 'E'))
        # Output: distances: {'A':0, 'B':3, 'C':2, 'D':5, 'E':6}
        # Path: A -> C -> B -> D -> E

Key design decisions: - Early negative-edge check: Iterates all edges once before running the main loop. Dijkstra's greedy relaxation fails on negative edges, so we bail early. - Standard heap relaxation: Each node may be pushed multiple times; we skip stale heap entries via if current_dist > distances[u]. - Predecessor map: Enables reconstruct_path() to retrieve the actual shortest path.