کوتاه‌ترین مسیر همه‌ی جفت‌ها با مربع‌سازی مکرر

برنامه‌نویسی پویا

کوتاه‌ترین مسیر بین همه‌ی جفت‌ها را با «ضرب» ماتریس وزن‌ها در خودش پیدا می‌کند، با min به جای جمع و + به جای ضرب؛ با مربع کردن مکرر، log n ضرب کافی است. Θ(n³ log n).

فرض کنید L^(m)[i][j] طول کوتاه‌ترین مسیر از i به j با حداکثر m یال باشد. مسیری با حداکثر 2m یال را می‌شود به دو نیمه‌ی حداکثر m یالی شکست:

ادامه‌ی توضیح ↓

زمان: Θ(n³ log n)
حافظه: Θ(n²)
CLRS، بخش ۲۳.۱

ورودی:

V=5 · E=9 · src=Aخروجی PDF

گراف پنج‌رأسی CLRS با یال‌های منفی (بدون دور منفی)؛ بعد از دو مربع‌سازی (m = ۴ = n − ۱) همه‌ی فاصله‌ها نهایی‌اند. سطرها و ستون‌ها به ترتیب A تا E اند.

def all_pairs(graph, src):
nodes = sorted(graph)
n = len(nodes)
inf = float("inf")
# L[i][j]: the shortest path from i to j using at most m edges; first m = 1, the edges themselves.
L = [[0 if i == j else inf for j in range(n)] for i in range(n)]
for u in graph:
for v, w in graph[u]:
L[nodes.index(u)][nodes.index(v)] = w
m = 1
while m < n - 1:
L = square(L, nodes)
m = 2 * m
return L
def square(L, nodes):
# A min-plus product: like matrix multiplication with + as "·" and min as "+".
n = len(L)
C = [[float("inf")] * n for _ in range(n)]
for i in range(n):
for j in range(n):
for k in range(n):
if L[i][k] + L[k][j] < C[i][j]:
C[i][j] = L[i][k] + L[k][j]
return C

ناوردا: بعد از هر مربع‌سازی، L[i][j] طول کوتاه‌ترین مسیر i به j با حداکثر m یال است.

شروع اجرا

جدول هنوز خالی است.

متغیرهای محلی

src'A'

نارنجی = در همین گام عوض شد

graph dict

'A': [('B', 3), ('C', 8), ('E', -4)]
'B': [('D', 1), ('E', 7)]
'C': [('B', 4)]
'D': [('A', 2), ('C', -5)]
'E': [('D', 6)]

Call stack

all_pairs()خط 1

گام ۱ از ۷۳۸

توضیح

ایده

L^(2m)[i][j] = min over k of  L^(m)[i][k] + L^(m)[k][j]

این دقیقاً ضرب ماتریس است، با min به جای جمع و + به جای ضرب (ضرب min-plus).

مربع‌سازی مکرر

اگر دور منفی نباشد، کوتاه‌ترین مسیر حداکثر n − 1 یال دارد. به جای n − 2 بار ضرب (L, L², L³, …) ماتریس را پشت سر هم مربع می‌کنیم: L, L², L⁴, L⁸, … تا وقتی m ≥ n − 1. پس ⌈log₂(n − 1)⌉ ضرب، هر کدام Θ(n³).

مقایسه

فلوید–وارشال همین کار را در Θ(n³) انجام می‌دهد؛ این روش بیشتر برای نشان دادن پیوند کوتاه‌ترین مسیر و ضرب ماتریس مهم است.

ورودی

یک گراف جهت‌دار؛ وزن منفی مجاز است، دور منفی نه. جدول L ماتریس فعلی و C حاصل ضرب در حال ساخت است؛ ترتیب سطرها و ستون‌ها ترتیب الفبایی رأس‌هاست.