Dijkstra

"""Unit 24 — Dijkstra: Basic Implementation
Topic : Dijkstra's Algorithm (Basic)
Time  : O((V + E) log V)
Space : O(V + E)

Description:
    Dijkstra based on a priority queue using heapq.
    Finds the shortest distance from a single starting point to all nodes.
    Works only on graphs without negative weights."""

import heapq
import sys

INF = sys.maxsize


def dijkstra(graph: list[list[tuple[int, int]]], src: int) -> list[int]:
    """Returns the single-source shortest path.

    Args:
        graph: adjacency list in the form graph[u] = [(v, weight), ...]
        src  : starting node (0-indexed)

    Returns:
        dist[v] = shortest distance from src to v (INF if unreachable)

    Time : O((V + E) log V)
    Space: O(V + E)"""
    n = len(graph)
    dist = [INF] * n
    dist[src] = 0

    #Insert into the heap in the form of (distance, node)
    heap: list[tuple[int, int]] = [(0, src)]

    while heap:
        d, u = heapq.heappop(heap)

        #Lazy Deletion: Skip nodes that have already been processed with a shorter distance
        if d > dist[u]:
            continue

        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))

    return dist


def build_graph(n: int, edges: list[tuple[int, int, int]],
                directed: bool = False) -> list[list[tuple[int, int]]]:
    """Creates an adjacency list from a list of edges.

    Args:
        n       : number of nodes (0-indexed: 0 ~ n-1)
        edges   : list of (u, v, weight)
        directed: True for directed graph, False for undirected graph

    Time : O(E)
    Space: O(V + E)"""
    graph: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((v, w))
        if not directed:
            graph[v].append((u, w))
    return graph


def main() -> None:
    #── Example 1: Graph from lecture text (1-indexed → 0-indexed conversion) ──
    #Nodes: 1~6 → 0~5
    #Edges: (u, v, w) (undirected)
    edges_ex1 = [
        (0, 1, 2),   # 1-2
        (0, 2, 1),   # 1-3
        (1, 2, 3),   # 2-3
        (1, 3, 5),   # 2-4
        (1, 4, 4),   # 2-5
        (2, 4, 1),   # 3-5
        (3, 5, 6),   # 4-6
        (4, 5, 2),   # 5-6
    ]
    graph1 = build_graph(6, edges_ex1, directed=False)
    dist1 = dijkstra(graph1, src=0)

    print("=" * 50)
    print("Example 1: Graph from lecture text (Start: Node 1)")
    print("=" * 50)
    for i, d in enumerate(dist1):
        label = str(d) if d < INF else "Unreachable"
        print(f"Node 1 → Node {i + 1}: {label}")

    #── Example 2: Directed graph ──
    print()
    print("=" * 50)
    print("Example 2: Directed graph (Start: Node 0)")
    print("=" * 50)
    edges_ex2 = [
        (0, 1, 4),
        (0, 2, 1),
        (2, 1, 2),
        (1, 3, 1),
        (2, 3, 5),
    ]
    graph2 = build_graph(4, edges_ex2, directed=True)
    dist2 = dijkstra(graph2, src=0)
    node_names = ["A", "B", "C", "D"]
    for i, d in enumerate(dist2):
        label = str(d) if d < INF else "Unreachable"
        print(f"  A → {node_names[i]}: {label}")

    #── Example 3: Including unreachable nodes ──
    print()
    print("=" * 50)
    print("Example 3: Including unreachable nodes")
    print("=" * 50)
    edges_ex3 = [(0, 1, 3), (1, 2, 2)]
    graph3 = build_graph(5, edges_ex3, directed=True)  #Nodes 3 and 4 are unreachable
    dist3 = dijkstra(graph3, src=0)
    for i, d in enumerate(dist3):
        label = str(d) if d < INF else "INF (unreachable)"
        print(f"  0 → {i}: {label}")


if __name__ == "__main__":
    main()

"""Chapter 24 — Dijkstra: Path Reconstruction
Topic : Dijkstra with Path Reconstruction
Time  : O((V + E) log V)
Space : O(V + E)

Explanation:
    By managing the prev[] array together, we can backtrack the shortest path.
    Whenever dist[v] is updated, record prev[v] = u.
    By following prev from the destination back to the source, the shortest path can be obtained."""

import heapq
import sys

INF = sys.maxsize


def dijkstra_with_path(
    graph: list[list[tuple[int, int]]],
    src: int,
) -> tuple[list[int], list[int]]:
    """Returns the shortest distance + path reconstruction information.

    Args:
        graph: graph[u] = [(v, weight), ...] adjacency list
        src  : source node (0-indexed)

    Returns:
        (dist, prev)
        dist[v] : shortest distance from src to v
        prev[v] : previous node of v in the shortest path (-1 if none)

    Time : O((V + E) log V)
    Space: O(V + E)"""
    n = len(graph)
    dist = [INF] * n
    prev = [-1] * n          #For path restoration: prev[v] = node just before v
    dist[src] = 0

    heap: list[tuple[int, int]] = [(0, src)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:      # lazy deletion
            continue

        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                prev[v] = u  #← Record path
                heapq.heappush(heap, (new_dist, v))

    return dist, prev


def reconstruct_path(prev: list[int], src: int, dst: int) -> list[int]:
    """Backtracks the prev array to return the path from src to dst.

    Args:
        prev: prev array returned by dijkstra_with_path
        src : source node
        dst : destination node

    Returns:
        List of nodes in the shortest path from src to dst (empty list if unreachable)

    Time : O(V)  (path length ≤ V)
    Space: O(V)"""
    if prev[dst] == -1 and dst != src:
        return []   #Unreachable

    path: list[int] = []
    cur = dst
    while cur != -1:
        path.append(cur)
        cur = prev[cur]

    path.reverse()
    return path


def main() -> None:
    #── Example graph (undirected) ──
    #Nodes: 0=A, 1=B, 2=C, 3=D, 4=E
    #
    #   A --4-- B --2-- D
    #   |      /        |
    #   2    1          3
    #   |  /            |
    #   C ------3------ E
    #
    n = 5
    edges = [
        (0, 1, 4),  # A-B
        (0, 2, 2),  # A-C
        (1, 2, 1),  # B-C
        (1, 3, 2),  # B-D
        (2, 4, 3),  # C-E
        (3, 4, 3),  # D-E
    ]

    graph: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))

    names = ["A", "B", "C", "D", "E"]
    src = 0   #Start: A

    dist, prev = dijkstra_with_path(graph, src)

    print("=" * 55)
    print(f"Start point: {names[src]}")
    print("=" * 55)
    print(f"{'Destination':>5} {'Shortest Distance':>8}  {'Path'}")
    print("-" * 55)

    for dst in range(n):
        d = dist[dst] if dist[dst] < INF else "INF"
        path = reconstruct_path(prev, src, dst)
        path_str = " → ".join(names[p] for p in path) if path else "Unreachable"
        print(f"  {names[src]} → {names[dst]}  {str(d):>6}    {path_str}")

    #── Detailed output for a specific path ──
    print()
    print("=" * 55)
    print("A → E Detailed Path")
    print("=" * 55)
    path_ae = reconstruct_path(prev, 0, 4)
    print(f"Path  : {' → '.join(names[p] for p in path_ae)}")
    print(f"Distance  : {dist[4]}")
    print()

    #── Unreachable cases ──
    print("=" * 55)
    print("Unreachable test (including isolated node)")
    print("=" * 55)
    graph2: list[list[tuple[int, int]]] = [[] for _ in range(3)]
    graph2[0].append((1, 5))  #Node 2 is isolated
    dist2, prev2 = dijkstra_with_path(graph2, 0)
    path2 = reconstruct_path(prev2, 0, 2)
    print(f"0 → 2: Distance={dist2[2]}, Path={path2 if path2 else 'Unreachable'}")


if __name__ == "__main__":
    main()

"""Chapter 24 — Dijkstra: Negative Edge Problem + Bellman-Ford Alternative
Topic : Negative Weights — Why Dijkstra Fails + Bellman-Ford
Time  : Dijkstra O((V+E) log V) / Bellman-Ford O(VE)
Space : O(V + E)

Description:
    Confirm directly why Dijkstra produces wrong answers when negative edges exist,
    and obtain the correct answer using the Bellman-Ford algorithm.
    Includes methods for detecting negative cycles."""

import heapq
import sys

INF = sys.maxsize


# ──────────────────────────────────────────────
#1. Dijkstra (Incorrect for negative edges)
# ──────────────────────────────────────────────

def dijkstra(graph: list[list[tuple[int, int]]], src: int) -> list[int]:
    """Basic Dijkstra (does not support negative edges).

    Time : O((V + E) log V)
    Space: O(V + E)"""
    n = len(graph)
    dist = [INF] * n
    dist[src] = 0
    heap: list[tuple[int, int]] = [(0, src)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            nd = dist[u] + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist


# ──────────────────────────────────────────────
#2. Bellman-Ford (Supports negative edges, detects negative cycles)
# ──────────────────────────────────────────────

def bellman_ford(
    n: int,
    edges: list[tuple[int, int, int]],
    src: int,
) -> tuple[list[int], bool]:
    """Bellman-Ford Algorithm.

    Args:
        n    : Number of nodes
        edges: List of directed edges (u, v, w)
        src  : Starting node

    Returns:
        (dist, has_negative_cycle)
        dist[v]            : Shortest distance from src to v
        has_negative_cycle : True if a negative cycle exists

    Time : O(V * E)  — Repeat relaxation V-1 times + 1 cycle check
    Space: O(V)"""
    dist = [INF] * n
    dist[src] = 0

    #Repeat V-1 times: The shortest path has V-1 or fewer edges
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:   #Early termination optimization
            break

    #If relaxation occurs in the V-th iteration, a negative cycle exists
    has_negative_cycle = False
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            has_negative_cycle = True
            break

    return dist, has_negative_cycle


# ──────────────────────────────────────────────
#3. Experiment
# ──────────────────────────────────────────────

def main() -> None:
    #── Case 1: Graph with negative edges ──
    # 0 ─4─▶ 1 ─(-3)─▶ 2
    # 0 ─2─▶ 2
    #
    #Actual shortest: 0→2 = 0+4+(-3) = 1
    #Dijkstra: First fixes 0→2 (2), so incorrect!
    print("=" * 55)
    print("Case 1: Graph with negative edges")
    print("  0 --4→ 1 --(-3)→ 2")
    print("  0 --2→ 2")
    print("=" * 55)

    edges1 = [(0, 1, 4), (1, 2, -3), (0, 2, 2)]
    n1 = 3

    #Graph for Dijkstra
    g_dijk = [[] for _ in range(n1)]
    for u, v, w in edges1:
        g_dijk[u].append((v, w))

    dist_dijk = dijkstra(g_dijk, 0)
    dist_bf, neg_cycle = bellman_ford(n1, edges1, 0)

    print(f"{'Node':>5} {'Dijkstra':>12} {'Bellman-Ford':>12} {'Correct?'}")
    print("-" * 50)
    for i in range(n1):
        d = dist_dijk[i] if dist_dijk[i] < INF else "INF"
        b = dist_bf[i] if dist_bf[i] < INF else "INF"
        correct = "✓" if d == b else "✗ Wrong!"
        print(f"  0 → {i}  {str(d):>10}  {str(b):>10}  {correct}")

    print(f"Negative cycle: {'Exists' if neg_cycle else 'None'}")

    #── Case 2: Negative cycle ──
    print()
    print("=" * 55)
    print("Case 2: Negative cycle graph")
    print("0 --1→ 1 --(-2)→ 2 --1→ 1  (Cycle: 1→2→1)")
    print("=" * 55)

    edges2 = [(0, 1, 1), (1, 2, -2), (2, 1, 1)]
    dist2, neg2 = bellman_ford(3, edges2, 0)
    print(f"Negative cycle detection: {'Exists → shortest distance undefined' if neg2 else 'None'}")

    #── Case 3: Normal (No negative edges) ──
    print()
    print("=" * 55)
    print("Case 3: Normal graph (No negatives) — both algorithms identical")
    print("=" * 55)

    edges3 = [(0, 1, 3), (0, 2, 1), (1, 3, 2), (2, 1, 1), (2, 3, 5)]
    n3 = 4
    g3 = [[] for _ in range(n3)]
    for u, v, w in edges3:
        g3[u].append((v, w))

    dist3_d = dijkstra(g3, 0)
    dist3_b, _ = bellman_ford(n3, edges3, 0)

    for i in range(n3):
        dd = dist3_d[i] if dist3_d[i] < INF else "INF"
        db = dist3_b[i] if dist3_b[i] < INF else "INF"
        print(f"0 → {i}: Dijkstra={dd}, Bellman-Ford={db}")

    #── Algorithm comparison summary ──
    print()
    print("=" * 55)
    print("Algorithm selection guide")
    print("=" * 55)
    print("No negative edges → Dijkstra  O((V+E) log V)")
    print("Negative edge exists     → Bellman-Ford   O(VE)")
    print("Detect negative cycle   → Bellman-Ford check on the V-th iteration")
    print("All-pairs shortest path     → Floyd-Warshall O(V³)")


if __name__ == "__main__":
    main()

"""Unit 24 — Dijkstra: Applications (K-th Shortest Path, State Graph)
Topic : Modified Dijkstra — K-th Shortest Path & State Graph
Time  : K-th Shortest: O(K * (V+E) log V) / State Graph: O((V*S+E) log(V*S))
Space : O(V + E) ~ O(V * S)

Explanation:
    1) K-th Shortest Path: When reaching the destination for the K-th time, it is the K-th shortest distance.
    2) State Graph Dijkstra: Expand nodes as (position, additional state)
       Example) Fuel limit, one-time toll-free coupon usage"""

import heapq
import sys

INF = sys.maxsize


# ──────────────────────────────────────────────
#1. K-th shortest path
# ──────────────────────────────────────────────

def kth_shortest_path(
    graph: list[list[tuple[int, int]]],
    src: int,
    dst: int,
    k: int,
) -> int:
    """Returns the K-th shortest path distance from src → dst.
    If unreachable or there are not K paths, returns INF.

    Principle:
      - Allow each node to be visited up to K times (visit_cnt[v] array)
      - When popping from the heap, increase visit_cnt[v]; skip if it exceeds K
      - The moment dst is popped for the K-th time, that distance is the K-th shortest distance

    Time : O(K * (V + E) log(KV))
    Space: O(K * V)"""
    n = len(graph)
    visit_cnt = [0] * n
    heap: list[tuple[int, int]] = [(0, src)]

    while heap:
        d, u = heapq.heappop(heap)
        visit_cnt[u] += 1

        if visit_cnt[u] > k:  #Exceed K times → skip
            continue
        if u == dst and visit_cnt[u] == k:
            return d

        for v, w in graph[u]:
            if visit_cnt[v] < k:
                heapq.heappush(heap, (d + w, v))

    return INF


# ──────────────────────────────────────────────
#2. State graph Dijkstra — one toll-free coupon
# ──────────────────────────────────────────────

def dijkstra_with_coupon(
    graph: list[list[tuple[int, int]]],
    src: int,
    dst: int,
) -> int:
    """Minimum cost from src→dst when you can use one toll-free coupon.

    State: (current node, whether coupon has been used)
    - Coupon unused: state=0
    - Coupon used: state=1

    dist[v][s]: minimum cost at node v with coupon state s

    Time : O((2*(V+E)) log(2V))
    Space: O(V)"""
    n = len(graph)
    # dist[node][coupon_used]
    dist = [[INF, INF] for _ in range(n)]
    dist[src][0] = 0
    # (cost, node, coupon_used)
    heap: list[tuple[int, int, int]] = [(0, src, 0)]

    while heap:
        cost, u, used = heapq.heappop(heap)
        if cost > dist[u][used]:
            continue

        for v, w in graph[u]:
            #Move without using coupon
            nc = cost + w
            if nc < dist[v][used]:
                dist[v][used] = nc
                heapq.heappush(heap, (nc, v, used))

            #Use coupon (only if not used yet)
            if used == 0:
                nc_free = cost  #This edge is free
                if nc_free < dist[v][1]:
                    dist[v][1] = nc_free
                    heapq.heappush(heap, (nc_free, v, 1))

    return min(dist[dst])


# ──────────────────────────────────────────────
#3. State graph Dijkstra — fuel limit
# ──────────────────────────────────────────────

def dijkstra_with_fuel(
    graph: list[list[tuple[int, int]]],
    fuel_graph: list[list[tuple[int, int]]],
    src: int,
    dst: int,
    max_fuel: int,
) -> int:
    """Shortest distance when fuel is consumed with each move and can only be recharged at specific nodes. 
    Simplified: fuel consumption = edge weight, fuel_graph is the set of charging nodes.

    Actual state: (node, current fuel)
    In this example, we only check the possibility of reaching with simple fuel limits.

    Time: O((V * F + E * F) log(V * F)) where F = max_fuel
    Space: O(V * F)"""
    n = len(graph)
    #dist[node][fuel]: minimum distance to this state
    dist = [[INF] * (max_fuel + 1) for _ in range(n)]
    dist[src][max_fuel] = 0
    heap: list[tuple[int, int, int]] = [(0, src, max_fuel)]

    refuel_nodes = {v for edges in fuel_graph for v, _ in edges}

    while heap:
        cost, u, fuel = heapq.heappop(heap)
        if cost > dist[u][fuel]:
            continue
        if u == dst:
            return cost

        for v, w in graph[u]:
            if fuel < w:
                continue  #Not enough fuel
            new_fuel = fuel - w
            #Refuel when reaching a charging node
            if v in refuel_nodes:
                new_fuel = max_fuel
            nc = cost + w
            if nc < dist[v][new_fuel]:
                dist[v][new_fuel] = nc
                heapq.heappush(heap, (nc, v, new_fuel))

    return INF


def main() -> None:
    #── K-th shortest path ──
    print("=" * 55)
    print("1. K-th shortest path (directed graph)")
    print("=" * 55)

    edges = [
        (0, 1, 1), (0, 2, 4),
        (1, 2, 2), (1, 3, 5),
        (2, 3, 1),
    ]
    n = 4
    g: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for u, v, w in edges:
        g[u].append((v, w))

    for k in range(1, 5):
        d = kth_shortest_path(g, 0, 3, k)
        label = str(d) if d < INF else "INF (none)"
        print(f"{k}-th shortest path (0→3): {label}")

    #── Toll-free coupon ──
    print()
    print("=" * 55)
    print("2. One toll-free coupon")
    print("=" * 55)

    # 0 --10-- 1 --10-- 3
    # |                 |
    # 1                 1
    # |                 |
    #2 ---1--- (highway, toll 100)--- 3
    edges2 = [
        (0, 1, 10), (1, 3, 10),
        (0, 2, 1),  (2, 3, 100),
    ]
    g2: list[list[tuple[int, int]]] = [[] for _ in range(4)]
    for u, v, w in edges2:
        g2[u].append((v, w))

    normal = INF  #Normal Dijkstra result
    heap_tmp: list[tuple[int, int]] = [(0, 0)]
    dist_tmp = [INF] * 4
    dist_tmp[0] = 0
    import heapq as hq
    while heap_tmp:
        d, u = hq.heappop(heap_tmp)
        if d > dist_tmp[u]:
            continue
        for v, w in g2[u]:
            if dist_tmp[u] + w < dist_tmp[v]:
                dist_tmp[v] = dist_tmp[u] + w
                hq.heappush(heap_tmp, (dist_tmp[v], v))
    normal = dist_tmp[3]

    coupon_result = dijkstra_with_coupon(g2, 0, 3)
    print(f"Without coupon 0→3: {normal}")
    print(f"With 1 coupon 0→3: {coupon_result}")
    print(f"Cost saving: {normal - coupon_result}")

    print()
    print("=" * 55)
    print("Summary of application patterns")
    print("=" * 55)
    print("K-th shortest: allow visit_cnt[v] <= K")
    print("Add state: extend dist with (node, state) as compound key")
    print("Coupon/fuel: add 1 dimension to state → O(V*S log(V*S))")


if __name__ == "__main__":
    main()