DP on Graphs with Cycles (Bellman–Ford & Layers) — சுழற்சி கிராஃப் DP

சுழற்சி — topo DP இல்லை; Bellman–Ford அல்லது கூடுதல் பரிமாணம்.

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

நாணய மீள்சுழற்சி; விளையாட்டு.

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

shortest path அல்லது வருகை வரம்பு.

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

def bellman_ford(n: int, edges: list[tuple[int, int, int]], src: int = 0) -> list[float]:
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist


print(bellman_ford(3, [(0, 1, 1), (1, 2, 1), (0, 2, 5)]))

அடிக்கடி நேரும் தவறுகள்

• முடிவில்லா தளர்வு.
• தவறான dp[node].

முக்கியச் சுருக்கக் குறிப்புகள்

• SCC சுருக்கம்.