أقصر المسارات الموزونة والإرخاء

import heapq
from math import inf

def dijkstra(graph, source):
    if source not in graph:
        raise ValueError("Unknown source")
    if any(weight < 0 for edges in graph.values() for _, weight in edges):
        raise ValueError("Dijkstra requires nonnegative weights")
    distance = {vertex: inf for vertex in graph}
    distance[source] = 0
    heap = [(0, source)]
    while heap:
        cost, vertex = heapq.heappop(heap)
        if cost != distance[vertex]:
            continue
        for neighbor, weight in graph[vertex]:
            candidate = cost + weight
            if candidate < distance[neighbor]:
                distance[neighbor] = candidate
                heapq.heappush(heap, (candidate, neighbor))
    return distance

graph = {"A": [("B", 9), ("C", 2)], "B": [], "C": [("B", 3)], "D": []}
print(sorted(dijkstra(graph, "A").items()))

[('A', 0), ('B', 5), ('C', 2), ('D', inf)]

تستقبل B أولا المسافة 9، ثم المسافة 5 عبر C. ويُتخطى الإدخال القديم ذي المسافة 9؛ وتبقى D غير قابلة للوصول.

from math import inf

def bellman_ford(vertices, edges, source):
    distance = {vertex: inf for vertex in vertices}
    if source not in distance:
        raise ValueError("Unknown source")
    distance[source] = 0
    for _ in range(len(vertices) - 1):
        changed = False
        for start, end, weight in edges:
            if distance[start] != inf and distance[start] + weight < distance[end]:
                distance[end] = distance[start] + weight
                changed = True
        if not changed:
            break
    for start, end, weight in edges:
        if distance[start] != inf and distance[start] + weight < distance[end]:
            raise ValueError("Reachable negative cycle")
    return distance

print(sorted(bellman_ford(["A", "B", "C"],
    [("A", "B", 4), ("A", "C", 5), ("B", "C", -2)], "A").items()))

[('A', 0), ('B', 4), ('C', 2)]

تصح الحافة السالبة هنا لأن الرسم لا يحوي دورة سالبة قابلة للوصول. لكنها تخالف الشرط المسبق المعلن لـ Dijkstra.