האלגוריתם הנתיב הקצר ביותר של דייקסטרה - מבוא מפורט וחזותי

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

אתה תלמד:

• מושגי גרף בסיסיים (סקירה מהירה).
• לשם מה משמש האלגוריתם של דייקסטרה.
• איך זה עובד מאחורי הקלעים עם דוגמה שלב אחר שלב.

בואו נתחיל. ✨

? מבוא לתרשימים

נתחיל בהקדמה קצרה לגרפים.

מושגי יסוד

גרפים הם מבני נתונים המשמשים לייצוג "חיבורים" בין זוגות אלמנטים.

• אלמנטים אלה נקראים צמתים . הם מייצגים אובייקטים, אנשים או ישויות מהחיים האמיתיים.
• החיבורים בין הצמתים נקראים קצוות .

זהו ייצוג גרפי של גרף:

צמתים מיוצגים בעיגולים צבעוניים וקצוות מיוצגים בקווים המחברים בין עיגולים אלה.

טיפ: שני צמתים מחוברים אם יש קצה ביניהם.

יישומים

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

סוגי גרפים

גרפים יכולים להיות:

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

טיפ: במאמר זה נעבוד עם גרפים לא מכוונים.

גרפים משוקללים

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

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

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

? מבוא לאלגוריתם של דייקסטרה

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

• תיקי מטרה ושימוש
• הִיסטוֹרִיָה
• יסודות האלגוריתם
• דרישות

תיקי מטרה ושימוש

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

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

הִיסטוֹרִיָה

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

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

במהלך ראיון בשנת 2001, ד"ר דייקסטרה גילה כיצד ומדוע תכנן את האלגוריתם:

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

⭐ לא יאומן, נכון? תוך 20 דקות בלבד עיצב ד"ר דייקסטרה את אחד האלגוריתמים המפורסמים ביותר בתולדות מדעי המחשב.

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

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

דרישות

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

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

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

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

יש לנו גרף זה:

האלגוריתם ייצור את הנתיב הקצר ביותר מצומת 0לכל שאר הצמתים בגרף.

טיפ: לגרף זה נניח כי משקל הקצוות מייצג את המרחק בין שני צמתים.

יהיה לנו הנתיב הקצר ביותר מצומת 0לצומת 1, מצומת 0לצומת 2, מצומת 0לצומת 3וכן הלאה לכל צומת בגרף.

בתחילה, יש לנו רשימת מרחקים זו (אנא עיין ברשימה למטה):

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

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

טיפ: זכור כי האלגוריתם הושלם לאחר שכל הצמתים נוספו לנתיב.

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

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

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

עלינו לעדכן את המרחקים מצומת 0לצומת 1ולצומת 2עם משקולות הקצוות המחברים אותם לצומת 0(צומת המקור). משקולות אלה הן 2 ו -6 בהתאמה:

לאחר עדכון המרחקים של הצמתים הסמוכים, עלינו:

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

אם נבדוק את רשימת המרחקים נוכל לראות שלצומת 1יש את המרחק הקצר ביותר לצומת המקור (מרחק של 2), לכן אנו מוסיפים אותו לנתיב.

בתרשים נוכל לייצג זאת בקצה אדום:

אנו מסמנים אותו בריבוע אדום ברשימה כדי לייצג שהוא "ביקר" וכי מצאנו את הנתיב הקצר ביותר לצומת זה:

אנו מוציאים את זה מרשימת הצמתים הלא-מוכנים:

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

צומת 3וצומת 2שניהם צמודים לצמתים שכבר נמצאים בנתיב מכיוון שהם מחוברים ישירות לצומת 0ולצומת 1, בהתאמה, כפי שניתן לראות בהמשך. אלה הצמתים שננתח בשלב הבא.

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

המרחק הזה הוא 7 . בואו נראה למה.

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

• עבור צומת 3: המרחק הכולל הוא 7 מכיוון שנוסיף את משקלי הקצוות היוצרים את הנתיב 0 -> 1 -> 3(2 לקצה 0 -> 1ו -5 לקצה 1 -> 3).

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

מרשימת המרחקים נוכל לזהות מיד שמדובר בצומת 2עם מרחק 6 :

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

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

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

אתה יכול לראות שיש לנו שני מסלולים אפשריים 0 -> 1 -> 3או 0 -> 2 -> 3. בואו נראה איך נוכל להחליט איזו היא הדרך הקצרה ביותר.

ל- Node 3כבר יש מרחק ברשימה שהוקלט בעבר ( 7, ראו את הרשימה למטה). מרחק זה היה תוצאה של שלב קודם, בו הוספנו את המשקולות 5 ו- 2 משני הקצוות שעלינו לעבור כדי ללכת בשביל 0 -> 1 -> 3.

אבל עכשיו יש לנו אלטרנטיבה אחרת. אם נבחר ללכת בשביל 0 -> 2 -> 3, נצטרך לעקוב אחרי שני קצוות 0 -> 2ועם 2 -> 3משקולות 6 ו -8 ,בהתאמה,המייצג מרחק כולל של 14 .

ברור שהמרחק הראשון (הקיים) קצר יותר (7 לעומת 14), לכן נבחר לשמור על הנתיב המקורי 0 -> 1 -> 3. אנו מעדכנים את המרחק רק אם הנתיב החדש קצר יותר.

לכן, אנו מוסיפים את הצומת הזו הנתיב באמצעות החלופה הראשונה: 0 -> 1 -> 3.

אנו מסמנים את הצומת הזה כמתבקר ומעבירים אותו מרשימת הצמתים הלא מוכנים:

כעת אנו חוזרים על התהליך שוב.

עלינו לבדוק את הצמתים החדשים הסמוכים שטרם ביקרנו בהם. הפעם, צמתים אלה הם צומת 4וצומת 5שכן הם צמודים לצומת 3.

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

• לצומת 4: המרחק הוא 17 מהנתיב   0 -> 1 -> 3 -> 4.
• לצומת 5: המרחק הוא 22 מהנתיב 0 -> 1 -> 3 -> 5.

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

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

אנו גם מסמנים את זה כ"ביקור "על ידי הוספת ריבוע אדום קטן ברשימה:

ואנחנו מוציאים את זה מרשימת הצמתים הלא מוכנים:

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

לצומת 5:

• האפשרות הראשונה היא לעקוב אחר הנתיב 0 -> 1 -> 3 -> 5, שמרחק 22 מצומת המקור (2 + 5 + 15). מרחק זה כבר נרשם ברשימת המרחקים בשלב קודם.
• האפשרות השנייה תהיה לעקוב אחר הנתיב 0 -> 1 -> 3 -> 4 -> 5, שמרחק 23 מצומת המקור (2 + 5 + 10 + 6).

ברור שהנתיב הראשון קצר יותר, לכן אנו בוחרים אותו לצומת 5.

לצומת 6:

• הנתיב הזמין הוא 0 -> 1 -> 3 -> 4 -> 6, שמרחק 19 מצומת המקור (2 + 5 + 10 + 2).

אנו מסמנים את הצומת עם המרחק הקצר ביותר (הידוע כיום) כביקור. במקרה זה, צומת 6.

ואנחנו מוציאים את זה מרשימת הצמתים הלא מוכנים:

עכשיו יש לנו את הנתיב הזה (מסומן באדום):

רק צומת אחד עדיין לא ביקר, צומת 5. בואו נראה איך נוכל לכלול את זה בנתיב.

ישנם שלושה נתיבים שונים שנוכל לנקוט כדי להגיע לצומת 5מהצמתים שנוספו לנתיב:

• אפשרות 1:0 -> 1 -> 3 -> 5 עם מרחק 22 (2 + 5 + 15).
• אפשרות 2:0 -> 1 -> 3 -> 4 -> 5 עם מרחק של 23 (2 + 5 + 10 + 6).
• אפשרות 3:0 -> 1 -> 3 -> 4 -> 6 -> 5 עם מרחק של 25 (2 + 5 + 10 + 2 + 6).

אנו בוחרים את הנתיב הקצר ביותר: 0 -> 1 -> 3 -> 5עם מרחק של 22 .

אנו מסמנים את הצומת כמתבקש ומעבירים אותו מרשימת הצמתים הבלתי נראים:

וואלה! יש לנו את התוצאה הסופית עם הנתיב הקצר ביותר מצומת 0לכל צומת בגרף.

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

לדוגמא, אם ברצונך להגיע לצומת 6החל מצומת 0, עליך רק לעקוב אחר הקצוות האדומים ותעקוב 0 -> 1 -> 3 -> 4 - > 6באופן אוטומטי אחר הנתיב הקצר ביותר .

בסיכום

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

אני באמת מקווה שאהבת את המאמר שלי ומצאת אותו מועיל. עכשיו אתה יודע איך האלגוריתם של דייקסטרה עובד מאחורי הקלעים. עקוב אחרי בטוויטר @ EstefaniaCassN ובדוק את הקורסים המקוונים שלי.