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

תבנית:לערוך {{#invoke:ParamValidator|validateparams|module_options=יחידה:PV-options}} {{#invoke:תבנית מידע|מידע| | טבלה-עיצוב = width: 22em; font-size: 95%; | כותרת תבנית-עיצוב =background: #B2C6FF; border:1px solid #aaaaaa; border-bottom:0px; | כותרת-עיצוב = background: #B2C6FF; | תמונה = קובץ:DijkstraDemo.gif | כיתוב=אנימציה להמחשת האלגוריתם. משקלי הקשתות שווים למרחק הגאומטרי ביניהן. | תווית-מידע10=מחלקה | תווית-מידע20=סוג | תווית-מידע30=מבנה נתונים | תווית-מידע40=סיבוכיות זמן |סיבוכיות זמן-ויקינתונים=P3752 | תווית-מידע50=סיבוכיות מקום |סיבוכיות מקום-ויקינתונים=P3755 | תווית-מידע60=ממציא |ממציא-ויקינתונים-מרובה=P61 |ממציא-ויקינתונים-פרטים=P577 | תווית-מידע70=נקרא על שם |נקרא על שם-ויקינתונים-מרובה=P138 | תווית-מידע80=הומצא |הומצא-ויקינתונים=P575

}}

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

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

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

הגדרות

האלגוריתם פועל על גרפים מכוונים או לא מכוונים, בעלי משקלים חיוביים.

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

המסלול הקל ביותר לקודקוד u מוגדר כמסלול מהמקור ל-u, כך שסכום משקלי הקשתות לאורך המסלול הוא מינימלי מבין כל המסלולים. סכום זה נקרא המרחק בין המקור ל-u.

בביטויי סיבוכיות, הביטויים E ו-V מתייחסים לגודל קבוצת הקודקודים והקשתות, ולא לקבוצות עצמן. למשל, O(V+E) הוא כתיב מקוצר של O(|V|+|E|).

האלגוריתם

פסאודו קוד

DistEst הוא מיפוי מקודקוד להערכת המרחק מהמקור. תבנית:כPrev הוא מיפוי מקודקוד לקודקוד שקודם לו במסלול הקל ביותר שהתגלה עד כה.

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

function Dijkstra(Graph, Source):
    for v in Graph.Vertices:
        DistEst[v] = ∞
        Prev[v] = NIL
    DistEst[Source] = 0
    Initialize min priority queue Q, with all graph vertices, keyed by their DistEst[v]

    while Q is not empty:
        u = Q.ExtractMin()
        for v adjacent to u:
            if DistEst[v] > DistEst[u] + Weight(u,v):
                -- a shorter path to v has been discovered!
                DistEst[v] = DistEst[u] + Weight(u,v)
                Prev[v] = u
                Q.DecreaseKey(v, DistEst[v])
    return DistEst, Prev

^[1]^[2]

הסבר ואינטואיציה

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

באתחול, כל הערכות המרחק מאותחלות כאינסוף, פרט להערכת המרחק למקור, שהיא 0 (המרחק מקודקוד לעצמו הוא 0).

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

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

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

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

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

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

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

דוגמת הרצה

אינטואיציה

דייקסטרה מגלה את המסלול הקל ביותר תחילה מהקודקודים הקרובים ביותר למקור, ולאחר מכן מקודקודים רחוקים יותר ויותר. למשל, בדוגמת ההרצה הנ"ל תחילה מתגלה המסלול מקודקוד שמרחקו מהמקור הוא 7, לאחר מכן 9, וכו'.^[3]

בגרף גאומטרי (משקלים=מרחק גאומטרי), בדומה לדוגמת ההרצה שמופיעה בראש הערך, ניתן לדמיין שמשרטטים עיגול מסביב למקור, ומגדילים הדרגתית את רדיוס העיגול. כשקודקוד נכנס לעיגול, דייקסטרה חישב את המסלול הקל ביותר אליו. ניתן להיעזר באנלוגיה הפיזיקלית הבאה: מתחילים להזרים מים לרשת תעלות (נניח שכל התעלות בעלות קיבולת זהה, ואין הבדלי גבהים). המים יבקרו בקודקודים באותו סדר שדייקסטרה מבקר בהם, וימצאו אותם מסלולים קצרים.^[4]^[5] זוהי מעין גרסה "ממושקלת" של חיפוש לרוחב (ראה פירוט בהמשך הערך).

תכונות

האלגוריתם מוצא עץ מסלולים מזעריים תבנית:אנ. זהו תת-גרף שהוא עץ שמושרש בקודקוד המקור, וכל מסלול מהשורש לכל קודקוד אחר הוא מסלול קל ביותר בגרף המקורי. אם הגרף קשיר, זהו עץ פורש.^[6]
סיבוכיות מקום: סיבוכיות המקום היא O(|V|), הנדרשים עבור תור הקדימויות Q והמילון DistEst.^[7]^[8]
אם אין מסלול מהמקור לקודקוד מסוים v, יתקיים DistEst[v]=inf ו-Prev[v]=nil.
הערכת המרחק תמיד גדולה או שווה למרחק האמיתי.^[9]

חמדנות ותכנון דינמי

תבנית:ראו גם מאחר שכל מסלול קל ביותר מכיל תת-מסלולים שגם הם מסלולים קלים, לבעיה יש תבנית:קישור שפה. כלומר, הפתרון יכול להבנות מפתרון בעיות קטנות יותר. בעיות מסוג זה מתאימות לפתרון בעזרת אלגוריתמים חמדניים ותכנון דינמי.^[10]^[11] החמדנות של האלגוריתם באה לידי ביטוי בכך שהאלגוריתם בוחר את הקודקוד שנראה בשלב הנוכחי כקרוב ביותר.^[11] ניתן לראות את הגישה החמדנית כפתרון יעיל של בעיית תכנון דינמי.^[12]

נכונות

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

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

כמו בפסאודו קוד הנ"ל, נסמן ב-DistEst[v] את הערכת המרחק מ-s ל-v. בנוסף, נסמן ב-TrueDist[v] את המרחק הקל ביותר מ-s ל-v.

בסיס האינדוקציה:

כשטרם נשלפו קודקודים מהתור, הטענה מתקיימת באופן ריק.

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

צעד האינדוקציה:

נניח שנשלפו k קודקודים, כך שלכולם האלגוריתם מצא את המסלול הקל ביותר האמיתי (הנחת האינדוקציה). נסמן ב-v את הקודקוד ה-k+1 שנשלף מהתור, ונוכיח שגם עבורו האלגוריתם מצא את המסלול הקל ביותר האמיתי.

יהי Q מסלול כלשהו מ-s ל-v. נוכיח שמשקלו איננו קטן משל $P_{v}$ .

נסמן ב-u את הקודקוד שקודם ל-v במסלול הקל ביותר שהאלגוריתם מצא עד כה (Prev[v] בפסאודו קוד הנ"ל). בנוסף נסמן ב-y את הקודקוד הראשון ב-Q שאיננו אחד מ-k הקודקודים הראשונים שנשלפו, וב-x את הקודקוד שלפני y במסלול Q.

בגלל שהקשת uv נשלפה מתור הקדימויות לפני xy, מתקיים $D i s t E s t [u] + w (u \to v) \leq D i s t E s t [x] + w (x \to y)$ (במילים: הערכת המשקלים של המסלול P קטנה או שווה להערכת המשקל של המסלול Q). אחרת x היה נשלף מתור הקדימויות לפני u.

לפי הנחת האינדוקציה והעובדה שהאלגוריתם כבר ביקר ב-u ו-x, ניתן להציב את TrueDist במקום DistEst: $T r u e D i s t [u] + w (u \to v) \leq T r u e D i s t [x] + w (x \to y)$ . כלומר, אפילו תת-המסלול של Q מ-s ל-y איננו עדיף על $P_{v}$ . הוספת הקשתות הנוספות במסלול Q רק יכולה להגדיל את המשקל.

ולכן המשקל של המסלול שאלגוריתם דייקסטרה מצא קטן או שווה לכל מסלול אחר מ-s ל-v.^[13]^[14]

איור להמחשת ההוכחה. המסלול הקצר ביותר שדייקסטרה מצא, P, מסומן בירוק. המסלול האדום הוא מסלול אלטרנטיבי, Q. חץ שבור מסמן תת-מסלול. באליפסה הכחלחלה יש את הקודקודים שהוצאו מהתור. אם אלגוריתם דייקסטרה בחר להגיע ל-v עם קשת uv, אז לא ייתכן שניתן למצוא מסלול קל יותר שעובר בקשת xy.תבנית:ביאור^[14]

קשתות שליליות

כאשר בגרף יש משקלים שליליים, לא מובטח שאלגוריתם דייקסטרה יימצא את המסלול הקצר ביותר.^[13]

בהוכחת הנכונות הנ"ל, הביטוי $D i s t E s t [u] + w (u \to v) \leq D i s t E s t [x] + w (x \to y)$ איננו נכון, משום שייתכן ש-w(xy) שלילי.^[13] במילים אחרות, דייקסטרה מניח שהמסלול הקל ביותר ל-v חייב לעבור בקודקודים שקרובים יותר למקור. אך כאשר יש צלעות שליליות, לא נכון להניח זאת.^[15]

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

דוגמה לגרף בעל משקלות שליליות, שבו דייקסטרה לא יצליח למצוא את המסלול הקל ביותר:דייקסטרה ישלוף מהתור את S ולאחר מכן את A. בשלב זה הוא ייקבע שהמסלול הקל ביותר ל-A הוא S->A, שמשקלו 3. אך למעשה יש מסלול קל יותר, שעובר בקשת שלילית: S->B->A, במשקל 2.^[15]

סיבוכיות זמן ובחירת מבנה נתונים לתור הקדימויותתבנית:ביאור

תבנית:חומר רקע מקוצר בביטויי הסיבוכיות בערך זה, V ו-E מתייחסים למספר הקודקודים והקשתות בגרף (בהתאמה), ולא לקבוצת הקודקודים\קשתות עצמה.

סיבוכיות זמן

ניתוח מקרה גרוע

כל קודקוד מוכנס ומוצא מתור הקדימיות בדיוק פעם אחת. בגרף מכוון, כל קשת תופיעה פעם אחת בלולאת ה-for (שורה 10), ולכן כמות הקריאות ל-DecreaseKey היא לכל היותר $E$ . לכן סיבוכיות הזמן במקרה הגרוע היא:^[16]^[17]

$O (I N I T I A L I Z E + V * E X T R A C T_M I N + E * D E C R E A S E_K E Y)$

נבחן כיצד הסיבוכיות תושפע מבחירת מבנה הנתונים לתור הקדימויות.

הבחירה הנאיבית ביותר היא רשימה (זהו גם המימוש שהיה ידוע בשנות החמישים, כשאלגוריתם דייקסטרה הומצא^[18]^[19]). עלות EXTRACT_MIN היא $O (V)$ , ו-DECREASE_KEY ב- $O (1)$ (בהנחה שהקודקודים ממוספרים, או שניתן להגיע אליהם בזמן קבוע באמצעות מצביע). סך הכל זמן הריצה של האלגוריתם הוא $O (V^{2})$ .^[17] אם הגרף צפוף מאוד ( $E = Θ (V^{2})$ ), אז זוהי הסיבוכיות הטובה ביותר האפשרית, משום שאי אפשר להתחמק מלסרוק את כל הקשתות בגרף.^[20] אך עבור המקרה הכללי, הומצאו מגוון תורי קדימויות יעילים יותר.^[19]

בחירה פופולרית^[21] היא ערימה בינארית, שהוצע על ידי וויליאמס ב-1964.^[19] בערימה בינארית האתחול לוקח זמן ליניארי, ופעולות ה-EXTRACT_MIN ו-DECREASE_KEY ניתנות לביצוע בזמן לוגריתמי. לכן הסיבוכיות הכוללת של האלגוריתם היא $O (E l o g V)$ תבנית:ביאור. סיבוכיות זו עדיפה על רשימה כל עוד $E = o (V^{2} / l o g V)$ .^[17] אופציה נוספת היא ערימה d-ארית, מעין הכללה של ערימה בינארית עם סיבוכיות דומה.^[22] על אף שזוהי לא הסיבוכיות מקרה גרוע הטובה ביותר, בפרקטיקה זו בחירה יעילה ופופולרית.^[21]

תורי הקדימויות המניבים את הסיבוכיות הטובה ביותר מסתמכים על ההבנחה הבאה: במקרה הגרוע, כמות הקריאות ל-DECRESE_KEY גדולה בסדר גודל מכמות הקריאות ל-EXTRACT_MIN (שכן כמות הקשתות בגרף יכולה להגיע לריבוע כמות הקודקודים). כלומר, יש יתרון לתור קדימויות שמאפשר לבצע את DECREASE_KEY בזמן קבוע, ומשאיר את EXTRACT_MIN בזמן לוגריתמי. בעזרת תור קדימויות כזה, אלגוריתם דייקסטרה רץ בזמן $O (V l o g V + E)$ .^[17]

ישנן מספר ערימות המתאימות לסיבוכיות זו: ערימת פיבונאצ'י (1984), אך נדרש להשתמש בניתוח לשיעורין;^[17]^[23] Relaxed heap תבנית:כ(1988), וריאציה של ערימת פיבונאצ'י שמתאימה לעיבוד מקבילי;^[24] תבנית:קישור שפה (1996), שאיננו משתמש בניתוח לשיעורין, אך הוא מורכב שלא לצורך, ומניח הנחות לא ריאליסטיות;^[19]^[25] ותבנית:קישור שפה (2012), שנועדה להיות אלטרנטביה פשוטה יותר לתורי ברודאל, ללא ניתוח לשיעורין או הנחות בעייתיות.^[19]^[26] נחקרו מגוון תורי קדימויות נוספים, שהם מחוץ להיקף הערך.

במודל החישובי הסטנדרטיתבנית:ביאור, לא ניתן לשפר את הסיבוכיות של אלגוריתם דייקסטרה מעבר ל-O(VlogV+E). אחרת, יופר החסם תחתון למיון $Ω (V l o g V)$ , שכן דייקסטרה סורק את הקודקודים לפי סדר מרחק עולה.^[27]^[28]תבנית:ביאור לכן דייקסטרה לא נופל מכל אלגוריתם מסלולים קלים אחר שמסתמך על מיון קודקודים.^[29]

סיבוכיות מקרה גרוע
מבנה נתונים	אתחול	EXTRACT_MIN	DECREASE_KEY	אלגוריתם דייקסטרה	הערות
רשימה^[17]^[30]	-תבנית:ביאור	$O (V)$	$O (1)$	$O (V^{2})$
ערימה בינארית^[17]	$O (V)$	$O (l o g V)$	$O (l o g V)$	$O (E l o g V)$ תבנית:ביאור
ערימת פיבונאצי^[17]^[30], relaxed heap^[24]	$O (V)$	$O (l o g V)$	$O (1)$	$O (V l o g V + E)$	ניתוח לשיעורין
תבנית:קישור שפה,^[19]^[30] תבנית:קישור שפה^[31]^[30]	$O (V)$	$O (l o g V)$	$O (1)$	$O (V l o g V + E)$

ביצועים פרקטיים וניתוח מקרה ממוצע

ערימת פיבונאצי (רגילה או חזקה) ותור ברודאל אינם נפוצים בפרקטיקה, משום שהם מורכבים למימוש וברוב המקרים אינם מניבים ביצועים טובים יותר (על אף הסיבוכיות מקרה גרוע הטובה יותר).^[16]^[32] הסיבות לפער בין הביצועים האמפיריים לסיבוכיות מקרה גרוע ביותר נובעת מגורמים קבועים משמעותיים ש"מוחבאים" בסימון האסימפטוטי, ומפער בין המקרה הגרוע ביותר למקרים נפוצים יותר.^[16]^[25]^[32]

נבחן למשל את תור הקדימויות שנבחר בספריות קוד פופולריות:תבנית:ביאור ערימה בינארית נבחרה בספריות בשפת פייתון (NetworkX),^[33] C#,^[34] ראסט,^[35] ו-Go^[36]; בעוד ש-Boost, ספריית C++ יעילה ופופולרית, משתמשת בערימה d-ארית (d=4).^[37]^[38]תבנית:ביאור העדפה זו נתמכת גם על ידי מחקרים אקדמיים שביצעו מבחנים אמפיריים.^[22]^[25]^[32]^[39]^[40]

ניתוח מקרה ממוצע עוזר לתת הסבר תאורטי לפער בין הביצועים בפרקטיקה לסיבוכיות מקרה גרוע. במקרה הגרוע נעשה מספר יוצא דופן של קריאות ל-DECREASE_KEY, ביחס למקרה הממוצע. בממוצע, מספר הקריאות הנוספות ל-DECREASE_KEY (ביחס ל-EXTRACT_MIN) איננו מספיק כדי להצדיק את הגדלת הגורמים הקבועים שנדרשים עבור EXTRACT_MIN (כפי שקורה בערימת פיבונאצ'י).^[32]^[16]

תבנית:קישור שפה וטרג'אן (1996) הראו שמספר הקריאות הצפוי ל-DECREASE_KEY חסום על ידי $O (V l o g (1 + E / V))$ , במודל בו ההנחה היחידה היא שעבור כל קודקוד, משקלי הקשתות מוגרלות באופן בלתי תלוי מאותה התפלגות. זמן הריצה הצפוי של אלגוריתם דייקסטרה עם ערימה בינארית הוא $O (E + V l o g V l o g (1 + E / V))$ לעומת $O (E + V l o g V)$ עם ערימת פיבונאצי. לערימת פיבונאצ'י יש יתרון (אסימפטוטי) רק כאשר $E = o (V l o g V l o g l o g V)$ , ואפילו אז היחס בין זמני הריצה הוא רק $o (l o g l o g V)$ , שבפרקטיקה זניח לעומת הגורמים הקבועים בערימת פיבונאצ'י.^[32]

יש וריאציה של אלגוריתם דייקסטרה בעלת זמן ריצה ממוצע ליניארי (כאשר ידוע חסם למשקל המקסימלי, והמשקלים מתפלגים אחיד).תבנית:ביאור^[41]^[42]

משקלים שלמים

אם המשקלים הם מספרים שלמים, יש תורי קדימויות מיוחדים שיכולים לשפר את הסיבוכיות.תבנית:ביאור

תבנית:קישור שפה מאפשר לדייקסטרה לרוץ בזמן O(E+V*C), שכן הוא מאפשר לבצע DECREASE_KEY ב-O(1) ו-EXTRACT_MIN ב- $O (\sqrt{C})$ .תבנית:ביאור תור דלי מנצל את כך שניתן לחלק את המפתחות בתור הקדימויות בין C+1 דליים (כאשר C הוא המשקל המקסימלי בגרף), שכל אחד מכיל רשימה מקושרת של קודקודים בעלי מפתח זהה. ייתכן שהמפתח המזוהה עם דלי ישתנה, אך תמיד יהיה צורך רק ב-C+1 דליים.^[41]^[43]

המפתחות בתור תמיד יהיו בטווח בין המינימום הנוכחי $m i n$ ל- $m i n + C$ , או שהמפתח אינסופי (האלגוריתם טרם סרק את הקודקוד). נוכיח טענה זו כתבנית:קישור שפה: באתחול טענה זו נכונה באופן טריויאלי. בכל איטרציה, בתחילתה מבוצע EXTRACT_MIN שאיננו מקטין את המינימום, ולכן לא מפר את השמורה; ו-DECREASE_KEY גם איננו מפר את השמורה, שכן המפתח החדש הוא: $D i s t E s t [u] + w e i g h t (u, v) = m i n + w e i g h t (u, v) \leq m i n + C$ .^[41]^[43]

תור דלי הוא דוגמה בסיסית לתבנית:קישור שפה, שהם תורי קדימויות המותאמים למקרים בהם ערך המינימום לא קוטן. הנחה זו מתאימה לדייקסטרה, שסורק קודקודים בסדר עולה של מרחקם מהמקור.^[41]^[43]

תור קדימויות מונוטוני נוסף הוא תבנית:קישור שפה, שמשפר את תור דלי בכך שדליים מכילים מספר מפתחות, אך דליים של מפתחות שקרובים יותר למינימום יהיו "צרים" יותר (יכילו פחות מפתחות). זמן הריצה של דייקסטרה עם ערימת בסיס הוא $O (E + V l o g C)$ , ואם משתמשים בערימת בסיס עם שתי רמות מתקבל זמן ריצה של $O (E + V l o g C / l o g l o g C)$ .^[41]^[43]תבנית:ביאור

עבור גרפים מכוונים, סיבוכיות המקרה הגרוע הטובה ביותר הושגה על ידי Thorup תבנית:אנ ב-2004: (O(E+Vloglog(min{V,C}).^[44]תבנית:ביאור תבנית:ביאור יש וריאציה של דייקסטרה בעלת זמן ריצה ממוצע ליניארי O(E).^[41] עבור גרפים לא מכוונים, ישנה אפילו וריאציה שרצה ב-O(E) במקרה הגרוע.^[45]

סיבוכיות מקרה גרוע (משקלים שלמים)
מבנה נתונים	EXTRACT_MIN	DECREASE_KEY	אלגוריתם דייקסטרה
תור דלי (שכבה אחת)^[43]	O(C)	O(1)	O(E+VC)
תור דלי (2 שכבות)^[43]	O(sqrt(C))	O(1)	$O (E + V \sqrt{C})$
תור דלי עם k שכבות^[43]	$O (k + C^{1 / k})$	O(k)	$O (k E + V (k + C^{1 / k}))$
ערימת בסיס (שכבה אחת)^[43]	O(logC)	O(1)	$O (E + V l o g C)$
ערימת בסיס (2 שכבות)^[43]	$O (l o g C / l o g l o g C)$	O(1)	$O (E + V l o g C / l o g l o g C)$
הערימה של Thorup תבנית:כ(2004)^[43]	O(1)	O(loglogV)	O(EloglogV)

יישומים

תבנית:להשלים

השוואה לאלגוריתמים אחרים

דייקסטרה כהכללה של אלגוריתם חיפוש לרוחב עבור גרפים ממושקלים

תבנית:ראו גם ניתן לראות את אלגוריתם דייקסטרה כהכללה של אלגוריתם חיפוש לרוחב עבור גרפים ממושקלים.^[4]^[46] בפרט, אלגוריתם דייקסטרה שקול לאלגוריתם חיפוש לרוחב בגרף שבו כל המשקלים שווים ל-1.^[46]^[47]

סיבוכיות אלגוריתם חיפוש לרוחב היא O(V+E),^[48] בהשוואה ל-O(VlogV+E) של דייקסטרה. כלומר, בעיית המסלול הקצר ביותר בגרף לא ממושקל היא קלה יותר מאשר בגרף ממושקל.

אלגוריתם חיפוש לרוחב יכול למצוא מסלול קצר ביותר בגרף ממושקל באופן הבא: ניצור גרף חדש, G', שבו עבור כל קשת e=uv ניצור w(e) קשתות חדשות בעלות משקל=1 המחברות את u ו-v דרך w(e)-1 "קודקודי דמה" חדשים. אך שיטה זו מגדילה משמעותית את גודל הגרף שעליו צריך לבצע חיפוש. ניתן לראות את דייקסטרה כאופטימיזציה של שיטה זו, אשר אינה דורשת הגדלה מלאכותית של הגרף.^[46]

גרפים בעלי משקלים שליליים

תבנית:הפניה לערך מורחב האלגוריתם הקלאסי לבעיה זו הוא אלגוריתם בלמן-פורד. נהוג ללמוד אלגוריתם זה לצד דייקסטרה בקורסי מבוא לאלגוריתמים רבים. בלמן-פורד דומה במובנים מסוימים לדייקסטרה: גם הוא מיישם את התבנית האלגוריתמית של פורד לאלגוריתמים למציאת המסלול הקצר ביותר (ראו בפרק ההיסטוריה),^[18] וגם הוא אלגוריתם חמדן המשתמש בתכנון דינמי.^[13]

סיבוכיות הזמן של אלגוריתם בלמן-פורד היא O(VE).^[49] זו הייתה הסיבוכיות מקרה גרוע הטובה ביותר שהייתה ידועה עד ל-2023, אז פורסם אלגוריתם אקראי בעל סיבוכיות זמן של Õ(EV^8/9)תבנית:ביאור בסבירות גבוהה.^[50] כלומר, בעיית המסלול הקצר ביותר היא קשה יותר כאשר יש בגרף משקלים שליליים.

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

שימוש ביוריסטיקות - A*

תבנית:הפניה לערך מורחב ניתן לראות את אלגוריתם A* כוראיציה של דייקסטרה שמשתמשת בפונקציית יוריסטיקה כדי למצוא יותר מהר את המסלול הקצר ביותר. באלגוריתם A* נשלף הקודוקד v שממזער את DistEst[v]+h(v), כאשר h היא פונקציית יוריסטיקה האומדת את המרחק מ-v לקודקוד היעד. השוו זאת לדייקסטרה, אשר שולף את הקודקוד שממזער את DistEst[v] בלבד.^[51] דייקסטרה שקול ל-A* אם בוחרים את פונקציית היוריסטיקה h(x)=0.

לעומת דייקסטרה, A* נועד למצוא את המסלול הקצר ביותר בין זוג קודקודים ספציפי, בעוד שדייקסטרה מסוגל לפתור גם את בעיית כל המסלולים הקצרים ממקור יחיד.^[51]

במקרים רבים היוריסטיקה מאפשרת לאלגוריתם לנצל ידע חיצוני על הקודקודים. למשל, אם הגרף מייצג מיקומים, ניתן להשתמש במרחק האוקלידי בין v ליעד בתור פונקציית היוריסטיקה. כך אלגוריתם החיפוש יודע לוותר מראש על כיווני חיפוש מיותרים, ו"לכוון" ליעד. עם זאת, כדי להבטיח פלט נכון, ישנם הגבלות מסוימות על פונקציית היוריסטיקה (ראו בערך על האלגוריתם), ועבור קלטים מסוימים פונקציית המרחק האוקלידי לא מקיימת תנאים אלו.^[51] קובץ:A Star Algorithm.webm

מקרים פרטיים

עבור גרף לא מכוון, יש אלגוריתם אקראי שרץ ב- $O (E \sqrt{l o g V \cdot l o g l o g V})$ בתבנית:קישור שפה (כלומר, כשהקלט שואף לאינסוף, ההסתברות שואפת ל-1). האלגוריתם הוא וריאציה על אלגוריתם דייקסטרה, שבה רק תת-קבוצה מצומצמת של הקודקודים נמצאת בתור הקדימויות.^[52]

בנוסף, ישנם מקרים פרטיים של גרפים מכוונים בהם ניתן למצוא אלגוריתם בעל סיבוכיות עדיפה מדייקסטרה. ישנם גם שיפורים עבור גרפים מישוריים, גרפים חסרי מעגלים, וקלט גאומטרי.^[53]^[54]

המצאת האלגוריתם

המחקר המתמטי המודרני על מציאת המסלול הקל ביותר בגרף בעל משקלים חיוביים החל בשנות החמישים של המאה ה-20. ב-1956 חוקר ממכון ראנד פרסם תבנית לאלגוריתמים למציאת המסלול הקל ביותר, שאלגוריתם דייקסטרה מיישם. אלגוריתם דייקסטרה פורסם באופן בלתי תלוי ב-1957 על ידי חוקרים ממכון CASE, ב-1959 בידי אדסחר דייקסטרה (שהגה את האלגוריתם כבר ב-1956) וב-1960 על ידי אנשי חקר ביצועים. בנוסף, בתעשייה נעשה שימוש באלגוריתם זהה או דומה, לפחות בפרויקט אחד.^[55]

פורד (1956): תבנית לאלגוריתמים למציאת המסלול הקל ביותר

תבנית:ראו גםב-1956 תבנית:קישור שפה ממכון ראנד תיאר תבנית לאלגוריתמים למציאת המסלול הקל ביותר. לתבנית זו תואמים אלגוריתם דייקסטרה, כמו גם אלגוריתם בלמן-פורד המסוגל לעבוד עם משקלים שליליים (וקרוי על שם פורד בזכות תבנית זו). אך התבנית היא כללית, ויכולה להתאים באותה מידה גם לאלגוריתמים בעלי סיבוכיות אקספוננציאלית.

התבנית של פורד:תבנית:מסגרתפורד לא ציין אף כלל לבחירת הקשת $u v$ . אלגוריתם דייקסטרה בוחר את הקשת $u v$ שממזערת את $d (u)$ .^[18]^[56]

אדסחר דייסקטרה (1956\1959)

תבנית:ראו גםדייסקטרה תכנן את האלגוריתם ב-1956, במטרה להציג את יכולות המחשב תבנית:קישור שפה בטקס החניכה החגיגי שלו. דייסקטרה רצה לבחור בעיה אלגוריתמית שגם קהל לא מתמטי יוכל להבין. הבעיה שבחר בה הייתה מציאת המסלול הקצר ביותר בין ערים הולנדיות.תבנית:ביאור דייסקטרה מספר שהוא תכנן את האלגוריתם בכ-20 דקות, בזמן הפסקת קפה שלקח כשעשה קניות עם ארוסתו. דייסקטרה האמין שדווקא משום שלא היה יכול להשתמש בעפרון ונייר, הוא אולץ לחשוב על אלגוריתם פשוט ואלגנטי.^[57]

דייסקטרה פרסם את האלגוריתם רק כ-3 שנים לאחר המצאתו, ב-1959. תיאור האלגוריתם התפרס על פני עמוד אחד בלבד, מתוך מאמר בן 2.5 עמודים שכלל גם תיאור של אלגוריתם גרפי נוסף.^[58] המאמר לא עסק בבחירת מימוש לתור הקדימויות (למעשה דייקסטרא כלל לא השתמש במונח זה),^[58] ולכן בטקסטים מודרניים לעיתים מתייחסים לסיבוכיות הזמן של האלגוריתם המקורי כ- $O (| V |^{2})$ .^[16]^[18]

דייסקטרה אמר שב-1956 "אלגוריתם למציאת המסלול הקל ביותר בקושי נחשב למתמטיקה: יש מספר סופי של מסלולים מ-A ל-B וברור שאחד מהם הוא הקצר ביותר, אז על מה כל המהומה?". דייקסטרא החליט לפרסם מאמר על האלגוריתם 3 שנים לאחר המצאתו, כאשר עורך של כתב עת חדש, שעסק גם בנושאים שכיום ייחשבו כחלק ממדעי המחשב,^[59] פנה לדייסקטרה ושאל אם יש לו מה לתרום לכתב העת.^[57]

בתחילת שנות השישים דייסקטרה נתקל לראשונה בטקסט שקורא לאלגוריתם על שמו, בספר לימוד גרמני.^[57]

מאמרים שפורסמו במקביל

במקביל לדייקסטרה, חוקרים אחרים פיתחו את האלגוריתם ופרסמו אותו.

ב-1957 התפרסם תיאור של האלגוריתם במאמר של חוקרים מתבנית:קישור שפה באוהיו.^[18] התיאור פורסם בדו"ח שנתי של פרויקט מחקר שבוצע עבור ה-Combat Development Department ב-Electronic Proving Ground של צבא ארצות הברית.^[18] המאמר לא התבלט בזמן פרסומו,^[60] אך בהסתכלות היסטורית הוא זכור כתגלית עצמאית של אלגוריתם דייקסטרה.^[18]

ב-1960 Whiting & Hillier פרסמו מאמר נוסף שתיאר את האלגוריתם.^[61]^[62]^[63] המאמר פורסם בכתב עת העוסק בחקר ביצועים, והמוטיבציה נבעה מבעיות תחבורה ותקשורת.^[61]

Dantzig פרסם אלגוריתם דומה ב-1960, אך הוא היה פחות יעיל.^[18]

LEO 1 ו-British Railways תבנית:כ(1955-1956)

LEO 1 היה מחשב בריטי שהחל לפעול ב-1951. המחשב היה שייך לתאגיד המזון J. Lyons and Co., שגם השכיר את שירותי המחשוב לגורמים אחרים. ב-1955 תבנית:קישור שפה שכרו את שירותי המחשוב לטובת חישוב המרחק בין תחנות הרכבת שלהם. בניסוח גרפי, זוהי הבעיה של מציאת המסלול הקצר ביותר בין כל זוג קודקודים. על הבעיה עבד רוג'ר קולמן, תחת ניהולו של דייוויד קמינר.

כחלק מפתרון הבעיה, פותח אלגוריתם שאפשר להחשיב כגרסה מוקדמת של אלגוריתם דייסקטרה. עם זאת, האלגוריתם של קולמן כלל הרבה התאמות לבעיה הספציפית של British Railways. בנוסף, האלגוריתם מעולם לא פורסם, והידע שלנו עליו מתבסס על ראיונות שחובבי היסטוריית מחשוב ערכו עם קולמן בשנות האלפיים. קולמן לא המשיך לעסוק במדעי המחשב, ועד לאותם ראיונות הוא לא ידע על קיומו של האלגוריתם של דייסקטרה ועל החשיבות ההיסטורית של המצאתו שלו.^[64]^[65]

ראו גם

בעיית המסלול הארוך ביותר

קישורים חיצוניים

תבנית:ויקישיתוף בשורה

תבנית:MathWorld
אלגוריתם דייקסטרה, מחברת קורס מבני נתונים ואלגוריתמים בוויקיספר
מימושים של האלגוריתם בעשרות שפות, באתר Rosetta Code תבנית:אנ
יישום המאפשר לראות הרצה של האלגוריתם בצורה אינטראקטיבית וויזואלית, באתר אוניברסיטת סן פרנסיסקו
"גילוי מחדש" של דייקסטרה באמצעות פיתח מונחה-בדיקות, בבלוג של תבנית:קישור שפה ("הדוד בוב")
וידאו

ביאורים

תבנית:ביאורים

הערות שוליים

תבנית:הערות שוליים

↑ מבוסס על Cormen et al. (2022), עמ' 620. פונקציות העזר שוטחו, השמות עובדו לשמות אינדיקטיביים יותר, והקבוצה S נמחקה משום שלא השפיעה על הפונקציונליות.
↑ תבנית:קישור כללי
↑ Mehlhorn & Sanders (2008), עמ' 198
↑ ^4.0 ^4.1 Cormen et al. (2022), עמ' 620
↑ תבנית:יוטיוב
↑ Cormen et al. (2022), עמ' 608
↑ תבנית:קישור כללי
↑ תבנית:קישור כללי
↑ Cormen et al. (2022), עמ' 611
↑ Cormen et al. (2022), עמ' 605-606
↑ ^11.0 ^11.1 תבנית:קישור כללי
↑ תבנית:צ-מאמר
↑ ^13.0 ^13.1 ^13.2 ^13.3 תבנית:קישור כללי
↑ ^14.0 ^14.1 תבנית:צ-ספר. ישנה מהדורה מתורגמת: פיתוח אלגוריתמים, בתרגום תמר אלמוג, 2010, הוצאת האוניברסיטה הפתוחה.
↑ ^15.0 ^15.1 תבנית:צ-ספר תבנית:עוגן
↑ ^16.0 ^16.1 ^16.2 ^16.3 ^16.4 תבנית:צ-ספר תבנית:עוגן
↑ ^17.0 ^17.1 ^17.2 ^17.3 ^17.4 ^17.5 ^17.6 ^17.7 Cormen et al. (2022), עמ' 623-624
↑ ^18.0 ^18.1 ^18.2 ^18.3 ^18.4 ^18.5 ^18.6 ^18.7 תבנית:צ-מאמר
↑ ^19.0 ^19.1 ^19.2 ^19.3 ^19.4 ^19.5 תבנית:צ-מאמר. המבוא של מאמר זה מכיל סקירה היסטורית.
↑ תבנית:צ-ספר
↑ ^21.0 ^21.1 עבור סימוכין לפופולריות, ראה בתת-פרק על ניתוח אמפירי וניתוח מקרה ממוצע.
↑ ^22.0 ^22.1 תבנית:צ-ספר
↑ תבנית:צ-מאמר
↑ ^24.0 ^24.1 תבנית:צ-מאמר
↑ ^25.0 ^25.1 ^25.2 תבנית:צ-מאמר
↑ תבנית:קישור כללי
↑ Tarajan et al 2024 pg 2
↑ תבנית:צ-מאמר
↑ תבנית:קישור כללי
↑ ^30.0 ^30.1 ^30.2 ^30.3 תבנית:צ-מאמר
↑ תבנית:צ-מאמר
↑ ^32.0 ^32.1 ^32.2 ^32.3 ^32.4 תבנית:צ-מאמר
↑ תבנית:קישור כללי
↑ תבנית:קישור כללי
↑ תבנית:קישור כללי
↑ תבנית:קישור כללי
↑ תבנית:צ-מאמר
↑ תבנית:קישור כללי
↑ תבנית:צ-מאמר
↑ תבנית:צ-מאמר
↑ ^41.0 ^41.1 ^41.2 ^41.3 ^41.4 ^41.5 Melhorn & Sanders (2008), Chapter 10.5: Monotone Integer Priority Queues
↑ תבנית:צ-מאמר
↑ ^43.00 ^43.01 ^43.02 ^43.03 ^43.04 ^43.05 ^43.06 ^43.07 ^43.08 ^43.09 תבנית:צ-מאמר
↑ תבנית:צ-מאמר
↑ תבנית:צ-מאמר
↑ ^46.0 ^46.1 ^46.2 Dasgupta et al. (2012), פרק 4.4
↑ תבנית:קישור כללי
↑ Cormen et al. (2022), עמ' 558
↑ תבנית:צ-ספר תבנית:עוגן
↑ תבנית:צ-מאמר
↑ ^51.0 ^51.1 ^51.2 תבנית:קישור כללי
↑ תבנית:צ-מאמר
↑ תבנית:צ-מאמר
↑ תבנית:צ-ספר
↑ לטענות בפסקה זו יש סימוכין בהמשך הפרק, במקומות המתאימים.
↑ L.R. Ford, Jr, Network Flow Theory, Paper P-923, The RAND Corporation, 1956.
↑ ^57.0 ^57.1 ^57.2 תבנית:צ-מאמר
↑ ^58.0 ^58.1 תבנית:צ-מאמר
↑ תבנית:קישור כללי
↑ למשל, בגוגל סקולר ישנם 0 ציטוטים של המאמר מלפני שנת 2000.
↑ ^61.0 ^61.1 תבנית:צ-מאמר
↑ תבנית:צ-ספר
↑ תבנית:צ-מאמר
↑ תבנית:צ-מאמר
↑ תבנית:יוטיוב

[1] מבוסס על Cormen et al. (2022), עמ' 620. פונקציות העזר שוטחו, השמות עובדו לשמות אינדיקטיביים יותר, והקבוצה S נמחקה משום שלא השפיעה על הפונקציונליות.

[2] תבנית:קישור כללי

[3] Mehlhorn & Sanders (2008), עמ' 198

[:9-4] 4.0 ^4.1 Cormen et al. (2022), עמ' 620

[5] תבנית:יוטיוב

[6] Cormen et al. (2022), עמ' 608

[7] תבנית:קישור כללי

[8] תבנית:קישור כללי

[9] Cormen et al. (2022), עמ' 611

[10] Cormen et al. (2022), עמ' 605-606

[:24-11] 11.0 ^11.1 תבנית:קישור כללי

[12] תבנית:צ-מאמר

[:5-13] 13.0 ^13.1 ^13.2 ^13.3 תבנית:קישור כללי

[:0-14] 14.0 ^14.1 תבנית:צ-ספר. ישנה מהדורה מתורגמת: פיתוח אלגוריתמים, בתרגום תמר אלמוג, 2010, הוצאת האוניברסיטה הפתוחה.

[:26-15] 15.0 ^15.1 תבנית:צ-ספר תבנית:עוגן

[:14-16] 16.0 ^16.1 ^16.2 ^16.3 ^16.4 תבנית:צ-ספר תבנית:עוגן

[:4-17] 17.0 ^17.1 ^17.2 ^17.3 ^17.4 ^17.5 ^17.6 ^17.7 Cormen et al. (2022), עמ' 623-624

[:1-18] 18.0 ^18.1 ^18.2 ^18.3 ^18.4 ^18.5 ^18.6 ^18.7 תבנית:צ-מאמר

[:8-19] 19.0 ^19.1 ^19.2 ^19.3 ^19.4 ^19.5 תבנית:צ-מאמר. המבוא של מאמר זה מכיל סקירה היסטורית.

[20] תבנית:צ-ספר

[:22-21] 21.0 ^21.1 עבור סימוכין לפופולריות, ראה בתת-פרק על ניתוח אמפירי וניתוח מקרה ממוצע.

[:17-22] 22.0 ^22.1 תבנית:צ-ספר

[23] תבנית:צ-מאמר

[:25-24] 24.0 ^24.1 תבנית:צ-מאמר

[:18-25] 25.0 ^25.1 ^25.2 תבנית:צ-מאמר

[26] תבנית:קישור כללי

[:21-27] Tarajan et al 2024 pg 2

[28] תבנית:צ-מאמר

[:15-29] תבנית:קישור כללי

[:7-30] 30.0 ^30.1 ^30.2 ^30.3 תבנית:צ-מאמר

[31] תבנית:צ-מאמר

[:16-32] 32.0 ^32.1 ^32.2 ^32.3 ^32.4 תבנית:צ-מאמר

[33] תבנית:קישור כללי

[34] תבנית:קישור כללי

[35] תבנית:קישור כללי

[36] תבנית:קישור כללי

[37] תבנית:צ-מאמר

[38] תבנית:קישור כללי

[39] תבנית:צ-מאמר

[40] תבנית:צ-מאמר

[:6-41] 41.0 ^41.1 ^41.2 ^41.3 ^41.4 ^41.5 Melhorn & Sanders (2008), Chapter 10.5: Monotone Integer Priority Queues

[42] תבנית:צ-מאמר

[:19-43] 43.00 ^43.01 ^43.02 ^43.03 ^43.04 ^43.05 ^43.06 ^43.07 ^43.08 ^43.09 תבנית:צ-מאמר

[44] תבנית:צ-מאמר

[:20-45] תבנית:צ-מאמר

[:10-46] 46.0 ^46.1 ^46.2 Dasgupta et al. (2012), פרק 4.4

[47] תבנית:קישור כללי

[48] Cormen et al. (2022), עמ' 558

[:23-49] תבנית:צ-ספר תבנית:עוגן

[50] תבנית:צ-מאמר

[:12-51] 51.0 ^51.1 ^51.2 תבנית:קישור כללי

[:11-52] תבנית:צ-מאמר

[53] תבנית:צ-מאמר

[54] תבנית:צ-ספר

[55] לטענות בפסקה זו יש סימוכין בהמשך הפרק, במקומות המתאימים.

[56] L.R. Ford, Jr, Network Flow Theory, Paper P-923, The RAND Corporation, 1956.

[:2-57] 57.0 ^57.1 ^57.2 תבנית:צ-מאמר

[:3-58] 58.0 ^58.1 תבנית:צ-מאמר

[59] תבנית:קישור כללי

[60] למשל, בגוגל סקולר ישנם 0 ציטוטים של המאמר מלפני שנת 2000.

[:13-61] 61.0 ^61.1 תבנית:צ-מאמר

[62] תבנית:צ-ספר

[63] תבנית:צ-מאמר

[64] תבנית:צ-מאמר

[65] תבנית:יוטיוב

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

[57]

[58]

[59]

[60]

[61]

[62]

[63]

[64]

[65]