Shortest Path — Dijkstra, Bellman-Ford, Floyd-Warshall, A*

import heapq


class WGraph:
    """Weighted graph — directed বা undirected"""
    def __init__(self, n, directed=False):
        self.n = n
        self.directed = directed
        self.adj = [[] for _ in range(n)]

    def add_edge(self, u, v, w):
        self.adj[u].append((v, w))
        if not self.directed:
            self.adj[v].append((u, w))

    # ---------------- Dijkstra (lazy deletion) ----------------
    def dijkstra(self, src):
        INF = float('inf')
        dist = [INF] * self.n
        parent = [-1] * self.n
        dist[src] = 0
        pq = [(0, src)]
        while pq:
            d, u = heapq.heappop(pq)
            if d != dist[u]:            # stale — নতুন, ভালো entry আগেই এসেছে
                continue
            for v, w in self.adj[u]:
                nd = d + w
                if nd < dist[v]:
                    dist[v] = nd
                    parent[v] = u
                    heapq.heappush(pq, (nd, v))
        return dist, parent

    # ---------------- Bellman-Ford ----------------
    def bellman_ford(self, src):
        INF = float('inf')
        dist = [INF] * self.n
        parent = [-1] * self.n
        dist[src] = 0
        for rnd in range(self.n - 1):
            changed = False
            for u in range(self.n):
                du = dist[u]
                if du == INF:
                    continue
                for v, w in self.adj[u]:
                    if du + w < dist[v]:
                        dist[v] = du + w
                        parent[v] = u
                        changed = True
            if not changed:             # গড় কেস: ২-৩ round-এই স্থিতি
                break
        else:
            rnd = self.n - 1
        # V-তম inspection: আরও relax হলে negative cycle
        for u in range(self.n):
            du = dist[u]
            if du == INF:
                continue
            for v, w in self.adj[u]:
                if du + w < dist[v]:
                    raise ValueError(f'negative cycle detected via edge {u}->{v}')
        return dist, parent

    # ---------------- Floyd-Warshall (all-pairs) ----------------
    def floyd_warshall(self):
        INF = float('inf'); n = self.n
        d = [[INF] * n for _ in range(n)]
        nxt = [[-1] * n for _ in range(n)]
        for i in range(n):
            d[i][i] = 0
            nxt[i][i] = i
        for u in range(n):
            for v, w in self.adj[u]:
                if w < d[u][v]:
                    d[u][v] = w
                    nxt[u][v] = v
        for k in range(n):
            dk = d[k]
            for i in range(n):
                dik = d[i][k]
                if dik == INF:
                    continue
                di = d[i]; ni = nxt[i]
                for j in range(n):
                    alt = dik + dk[j]
                    if alt < di[j]:
                        di[j] = alt
                        ni[j] = ni[k]   # i থেকে j যাব k-এর পথ ধরে
        return d, nxt


def restore_path(nxt, u, v):
    """Floyd-Warshall-এর next-hop matrix থেকে আসল i→j পথ"""
    if nxt[u][v] == -1:
        return None
    path = [u]
    while u != v:
        u = nxt[u][v]
        path.append(u)
    return path


# ---------------- A* on grid ----------------

def astar(walls, start, goal, W, H):
    def h(c):                            # admissible: grid-এ সোজা পথের lower bound
        return abs(c[0] - goal[0]) + abs(c[1] - goal[1])
    g = {start: 0}
    parent = {start: None}
    pq = [(h(start), 0, start)]
    while pq:
        f, gg, u = heapq.heappop(pq)
        if u == goal:
            path, cur = [], u
            while cur is not None:
                path.append(cur); cur = parent[cur]
            return gg, path[::-1], len(g)
        if gg > g.get(u, float('inf')):
            continue                     # stale
        x, y = u
        for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
            v = (x+dx, y+dy)
            if not (0 <= v[0] < W and 0 <= v[1] < H) or v in walls:
                continue
            ng = gg + 1
            if ng < g.get(v, float('inf')):
                g[v] = ng; parent[v] = u
                heapq.heappush(pq, (ng + h(v), ng, v))
    return None, None, len(g)


# ================= unit cases =================
if __name__ == '__main__':
    # ১. CLRS-ধাঁচের graph — চারজন cross-validation
    g = WGraph(5, directed=True)
    for u, v, w in [(0,1,10),(0,2,3),(1,2,1),(2,1,4),(1,3,2),(2,3,8),(3,4,7),(2,4,2)]:
        g.add_edge(u, v, w)
    dd, _ = g.dijkstra(0)
    db, _ = g.bellman_ford(0)
    df, nxt = g.floyd_warshall()
    assert dd == db == df[0], 'তিন algorithm disagree!'
    assert dd == [0, 7, 3, 9, 5]
    assert restore_path(nxt, 0, 3) == [0, 2, 1, 3]

    # ২. negative edge — Bellman-Ford ঠিক, Dijkstra ভুল দিতে পারে
    neg = WGraph(3, directed=True)
    neg.add_edge(0, 1, 4)
    neg.add_edge(0, 2, 3)
    neg.add_edge(1, 2, -4)
    dn, _ = neg.dijkstra(0)
    dbn, _ = neg.bellman_ford(0)
    print(f'  negative-edge case: Dijkstra={dn}  (lucky/correct here)')
    print(f'  negative-edge case: Bellman-Ford={dbn}')
    assert dbn == [0, 4, 0]

    # ৩. negative cycle — ধরা পড়তেই হবে
    cyc = WGraph(3, directed=True)
    cyc.add_edge(0, 1, 1)
    cyc.add_edge(1, 2, -3)
    cyc.add_edge(2, 1, 1)                # 1→2→1 = -2 per lap
    try:
        cyc.bellman_ford(0)
        assert False, 'negative cycle ধরা পড়েনি!'
    except ValueError as e:
        print(f'  caught as expected: {e}')

    # ৪. A* maze — optimal length Dijkstra-র সমান, expansion কম
    import random
    random.seed(3)
    W = H = 25
    walls = {(random.randrange(W), random.randrange(H)) for _ in range(180)}
    start, goal = (0, 0), (W-1, H-1)
    walls.discard(start); walls.discard(goal)

    def dij_len():
        import heapq
        dist = {start: 0}; exp = 0; pq = [(0, start)]
        while pq:
            d, u = heapq.heappop(pq); exp += 1
            if u == goal: return d, exp
            if d > dist.get(u, float('inf')): continue
            x, y = u
            for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
                v = (x+dx, y+dy)
                if 0 <= v[0] < W and 0 <= v[1] < H and v not in walls:
                    nd = d + 1
                    if nd < dist.get(v, float('inf')):
                        dist[v] = nd; heapq.heappush(pq, (nd, v))
        return None, exp

    dl, de = dij_len()
    al, apath, touched = astar(walls, start, goal, W, H)
    assert dl == al, 'A* suboptimal?!'
    print(f'  maze: both length {dl}; Dijkstra expanded {de}, A* touched {touched}')

    print('সব unit case পাস')

নিজে বাড়ান:

১. dijkstra-তে indexed decrease-key version যোগ করুন (position map সহ) — একই input-এ heap op count দুই version-এর গুনে experiment table হালনাগাদ করুন। ২. Johnson’s algorithm preview: সব vertex-এ একটা virtual source যোগ করে Bellman-Ford একবার চালিয়ে re-weighting potential বানান, তারপর V-বার Dijkstra — sparse all-pairs-এ FW-কে হারায় কি না মেপুন। ৩. Currency arbitrage detector: rates dict থেকে w = -log(rate) graph বানিয়ে Bellman-Ford চালান — negative cycle পেলে cycle path print করুন (parent-chain থেকে)।