אלגוריתם פלויד-וורשאל

אלגוריתם פלויד-וורשאל הוא אלגוריתם במדעי המחשב המשמש למציאת המסלולים הקצרים ביותר בין כל שני זוגות צמתים, בגרף ממושקל ומכוון. האלגוריתם מבוסס על פרדיגמת התכנון הדינמי. האלגוריתם פועל גם על גרפים שמכילים קשתות עם משקלים שליליים, בניגוד לאלגוריתם דייקסטרה, אבל לא על גרפים עם מעגל שלילי. סיבוכיות זמן הריצה של האלגוריתם היא .

האלגוריתם פורסם על ידי רוברט פלויד בשנת 1962 בגרסתו המוכרת לנו כיום, אך גרסאות דומות של האלגוריתם פורסמו ב-1959 על ידי ברנארד רוי, ועל ידי סטיבן וורשאל ב-1962 במטרה לחשב את הסגור הטרנזיטיבי של קבוצת קודקודים בגרף[1].

Other Languages