خوارزمية Bellman-Ford Bellman-Ford Algorithm

الصياغة

for _ in range(num_nodes - 1):
    for u, v, weight in edges:
        if dist[u] + weight < dist[v]:
            dist[v] = dist[u] + weight

📄 مثال

def bellman_ford(edges, num_nodes, start):
    dist = {n: float("inf") for n in range(num_nodes)}
    dist[start] = 0
    for _ in range(num_nodes - 1):
        for u, v, weight in edges:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
    for u, v, weight in edges:
        if dist[u] + weight < dist[v]:
            raise ValueError("يوجد دورة سالبة")
    return dist

edges = [(0, 1, 4), (0, 2, 5), (1, 3, -3), (2, 3, 2)]
print(bellman_ford(edges, 4, 0))  # {0: 0, 1: 4, 2: 5, 3: 1}

أهم النقاط

💡 نصائح عملية

• استخدم Dijkstra افتراضيًا للأداء، وانتقل لـ Bellman-Ford فقط عند احتمال وجود أوزان سالبة أو حاجة لكشف دورة سالبة

⚠️ أخطاء شائعة

• نسيان جولة الاسترخاء الإضافية لكشف الدورة السالبة — يقبل نتائج قد تكون خاطئة تمامًا بصمت لو وُجدت دورة سالبة فعلًا

خصائص ذات صلة