Shortest Paths on a DAG — அடிப்படை

Shortest Paths on a DAG — வரைபடத்தில் முக்கியமான நுட்பம்.

உண்மை உலகில் இது ஏன் முக்கியம்?

வரைபடம், சமூக வலை, சார்பு அமைப்பு — தலைகோடுகள்/விளிம்புகள் மாதிரி.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

தளர்வு; DAG topo; parent பாதை.

Pythonில் முயற்சி செய்வோம்

import heapq


def dijkstra(adj: list[list[tuple[int, int]]], start: int) -> list[int]:
    n = len(adj)
    dist = [10**18] * n
    dist[start] = 0
    pq: list[tuple[int, int]] = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist


print(dijkstra([[(1, 4), (2, 1)], [(3, 1)], [(3, 2)]], 0))

பொதுவான தவறுகள்

• எதிர்மறை Dijkstra.
• INF.

முக்கிய பாடங்கள்

• நிலை Dijkstra.
• k-விளிம்பு BFS.