بستار تراگذری (وارشال)

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

برای هر جفت گره تعیین می‌کند آیا از اولی به دومی راهی هست؛ مثل فلوید–وارشال ولی با «یا» و «و» به جای کمینه و جمع.

بستار تراگذری یک رابطه (یا گراف جهت‌دار) می‌گوید از هر گره به کدام گره‌ها راهی هست. وارشال همان ایده‌ی فلوید–وارشال را با مقدارهای درست/نادرست به کار می‌برد:

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

زمان: O(V³)
حافظه: O(V²)
گریمالدی، فصل ۷
جانسون‌باو، فصل ۳
CLRS، بخش ۲۳.۲

ورودی:

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

پنج گره؛ از A به همه می‌شود رسید، ولی از E به هیچ‌جا جز خودش نمی‌شود.

def warshall(graph, src):
reach = {u: {v: False for v in graph} for u in graph}
for u in graph:
reach[u][u] = True
for v, _ in graph[u]:
reach[u][v] = True
from_src = reach[src]
for k in graph:
row_k = reach[k]
for i in graph:
if not reach[i][k]:
continue
for j in graph:
if reach[i][j]:
continue
if row_k[j]:
reach[i][j] = True
return reach

ناوردا: بعد از دور k، reach[i][j] درست است اگر و فقط اگر مسیری از i به j باشد که ایستگاه‌های میانی‌اش فقط از گره‌های تا k باشند.

شروع اجرا

گره‌ی جاری (k)
درخت کوتاه‌ترین مسیر تا اینجا
یالِ در حال بررسی

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

src'A'

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

graph dict

'A': [('B', 1)]
'B': [('C', 1)]
'C': [('A', 1), ('D', 1)]
'D': [('E', 1)]
'E': []

Call stack

warshall()خط 1

گام ۱ از ۳۸۴

رشد تعداد عملیات با اندازه‌ی ورودی

میانگین ۵ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

check
ورودی فعلی (n=5)

نمایش به شکل جدول

n	check
4	39.2
8	244.8
12	583.2

توضیح

ایده

reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])

در دور k، گره‌ی k اجازه دارد ایستگاه میانی باشد.

کاربرد

در ریاضیات گسسته: بستار تراگذری یک رابطه روی مجموعه (ماتریس رابطه).
در برنامه‌ها: وابستگی‌ها («چه چیزهایی باید قبل از این ساخته شوند؟»).

هزینه

سه حلقه‌ی تودرتو: O(V³). اگر گراف پراکنده باشد، اجرای BFS از هر گره (O(V·(V+E))) سریع‌تر است.

در trace به چه چیزی نگاه کنی

برچسب کنار هر گره نشان می‌دهد آیا گره‌ی اول به آن می‌رسد؛ کل ماتریس reach در پنل حافظه است.