Shortest Path

from collections import defaultdict

# Weighted directed graph as adjacency list
# graph[u] = [(v, weight), ...]
graph = defaultdict(list)
edges = [
    ("A", "B", 4), ("A", "C", 2),
    ("B", "D", 5), ("C", "B", 1),
    ("C", "D", 8), ("D", "E", 2),
    ("B", "E", 6),
]
for u, v, w in edges:
    graph[u].append((v, w))

# Find shortest path from A to E
# Expected: A→C→B→D→E = 2+1+5+2 = 10

import heapq

def dijkstra(graph, start):
    dist = {start: 0}
    heap = [(0, start)]        # (distance, vertex)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float('inf')):
            continue           # stale entry — skip
        for v, w in graph[u]:
            new_dist = d + w
            if new_dist < dist.get(v, float('inf')):
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))

    return dist

distances = dijkstra(graph, "A")
print(distances)
# {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10}

# Reconstruct path
def dijkstra_path(graph, start, end):
    dist = {start: 0}
    prev = {start: None}
    heap = [(0, start)]

    while heap:
        d, u = heapq.heappop(heap)
        if u == end:
            break
        if d > dist.get(u, float('inf')):
            continue
        for v, w in graph[u]:
            new_dist = d + w
            if new_dist < dist.get(v, float('inf')):
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(heap, (new_dist, v))

    path = []
    node = end
    while node is not None:
        path.append(node)
        node = prev.get(node)
    path.reverse()
    return path, dist.get(end, float('inf'))

path, cost = dijkstra_path(graph, "A", "E")
print(path, cost)   # ['A', 'C', 'B', 'D', 'E'] 10

Start: A,  dist={A:0}
heap: [(0,A)]

Pop (0,A): process A's edges
  A→B w=4: dist[B]=4,  push (4,B)
  A→C w=2: dist[C]=2,  push (2,C)
heap: [(2,C),(4,B)]

Pop (2,C): process C's edges
  C→B w=1: 2+1=3 < 4  → dist[B]=3, push (3,B)
  C→D w=8: dist[D]=10, push (10,D)
heap: [(3,B),(4,B),(10,D)]

Pop (3,B): process B's edges
  B→D w=5: 3+5=8 < 10 → dist[D]=8,  push (8,D)
  B→E w=6: 3+6=9      → dist[E]=9,  push (9,E)

Pop (4,B): stale (4 > dist[B]=3) → skip

Pop (8,D): process D's edges
  D→E w=2: 8+2=10 > dist[E]=9 → no update

Pop (9,E): done — dist[E]=9... wait, A→C→B→E = 2+1+6=9
Actually: A→C→B→D→E = 2+1+5+2=10, A→C→B→E = 9. Dist[E]=9.

def bellman_ford(vertices, edges, start):
    """
    edges: list of (u, v, weight)
    Returns dist dict or raises ValueError on negative cycle.
    """
    dist = {v: float('inf') for v in vertices}
    dist[start] = 0

    # Relax all edges V-1 times
    for _ in range(len(vertices) - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Check for negative cycles (V-th relaxation should change nothing)
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            raise ValueError("Graph contains a negative-weight cycle")

    return dist

# Example with negative edge
vertices = ["A", "B", "C", "D"]
edges    = [("A","B",4), ("A","C",2), ("C","B",-3), ("B","D",5)]
print(bellman_ford(vertices, edges, "A"))
# {'A': 0, 'B': -1, 'C': 2, 'D': 4}