אלגוריתם דייקסטרה

מוצא את המסלול הקצר ביותר בין צמתים בגרף עם משקלים אי־שליליים.

שלב 1 מתוך 13

אתחול. המרחק ל־"A" = 0; כל השאר = ∞.

מרחקים

A	0
B	∞
C	∞
D	∞
E	∞

תור עדיפויות

Aמרחק = 0

▶אלגוריתם

dist[s] = 0; dist[v] = ∞ for all v ≠ s
enqueue (s, 0)
while queue not empty:
u ← extract-min(); mark settled
for each neighbor v of u:
if dist[u] + w(u,v) < dist[v]:
  dist[v] = dist[u] + w; enqueue v
// all reachable nodes settled

מקרא

מתייצב (פעיל)

בתור

התייצב ✓

Numbers below nodes show current shortest distance from A.

1 / 13מהירות