אלגוריתם הנתיב הקצר ביותר של דייקסטרה בג'אווה
1. סקירה כללית
הדגש במאמר זה הוא בעיית הדרך הקצרה ביותר (SPP), בהיותה אחת הבעיות התיאורטיות הבסיסיות הידועות בתורת הגרפים, וכיצד ניתן להשתמש באלגוריתם Dijkstra כדי לפתור אותה.
המטרה הבסיסית של האלגוריתם היא לקבוע את הנתיב הקצר ביותר בין צומת התחלה לשאר הגרף.
2. בעיית הנתיב הקצרה ביותר עם דייקסטרה
בהינתן גרף משוקלל חיובי וצומת התחלה (A), דייקסטרה קובע את הנתיב והמרחק הקצרים ביותר מהמקור לכל היעדים בגרף:
הרעיון המרכזי של האלגוריתם Dijkstra הוא לחסל ברציפות נתיבים ארוכים יותר בין הצומת ההתחלתי לבין כל היעדים האפשריים.
כדי לעקוב אחר התהליך, עלינו להחזיק שתי קבוצות נפרדות של צמתים, מסודרות ולא מסודרות.
צמתים מסודרים הם אלה עם מרחק מינימלי ידוע מהמקור. קבוצת הצמתים הלא מסודרת אוספת צמתים אליהם אנו יכולים להגיע מהמקור, אך איננו יודעים מה המרחק המינימלי מצומת ההתחלה.
להלן רשימת הצעדים שיש לבצע כדי לפתור את ה- SPP עם Dijkstra:
- הגדר מרחק ל startNode לאפס.
- הגדר את כל שאר המרחקים לערך אינסופי.
- אנו מוסיפים את startNode לקבוצת הצמתים המעורערים.
- בעוד מערך הצמתים המעורער אינו ריק אנו:
- בחר צומת הערכה מתוך מערך הצמתים הלא מסודרים, צומת ההערכה צריך להיות זה שהמרחק הנמוך ביותר הוא מהמקור.
- חישוב מרחקים חדשים לשכנים ישירים על ידי שמירה על המרחק הנמוך ביותר בכל הערכה.
- הוסף שכנים שעדיין לא התיישבו לקבוצת הצמתים הלא מסודרים.
ניתן לאגד את השלבים הללו לשני שלבים, אתחול והערכה. בואו נראה איך זה חל על גרף הדוגמה שלנו:
2.1. אִתחוּל
לפני שנתחיל לחקור את כל הנתיבים בגרף, ראשית עלינו לאתחל את כל הצמתים במרחק אינסופי וקודם לא ידוע, למעט המקור.
כחלק מתהליך האתחול, עלינו להקצות את הערך 0 לצומת A (אנו יודעים שהמרחק מצומת A לצומת A הוא 0 כמובן)
לכן, כל צומת בשאר הגרף יובחן בקודם ובמרחק:
כדי לסיים את תהליך האתחול, עלינו להוסיף את הצומת A לצמתים הלא מסודרים, להגדיר אותו כדי להיבחר ראשון בשלב ההערכה. זכור, ערכת הצמתים המסודרת עדיין ריקה.
2.2. הַעֲרָכָה
כעת לאחר שאותחלנו הגרף שלנו, אנו בוחרים את הצומת עם המרחק הנמוך ביותר מהסט הלא מסודר, ואז אנו מעריכים את כל הצמתים הסמוכים שאינם נמצאים בצמתים קבועים:
הרעיון הוא להוסיף את משקל הקצה למרחק צומת ההערכה, ואז להשוות אותו למרחק היעד. לְמָשָׁל עבור צומת B, 0 + 10 נמוך מ- INFINITY, ולכן המרחק החדש לצומת B הוא 10, והקודם החדש הוא A, הדבר תקף לגבי צומת C.
לאחר מכן מועבר צומת A מהצמתים הלא מסודרים לצמתים המסודרים.
צמתים B ו- C מתווספים לצמתים הלא מסודרים מכיוון שניתן להגיע אליהם, אך יש להעריך אותם.
כעת, כשיש לנו שני צמתים במערך הלא מסודר, אנו בוחרים את אחד עם המרחק הנמוך ביותר (צומת B), ואז אנו חוזרים על עצמנו עד שניישב את כל הצמתים בתרשים:
להלן טבלה המסכמת את האיטרציות שבוצעו במהלך שלבי הערכה:
| איטרציה | לֹא יַצִיב | מְיוּשָׁב | EvaluationNode | א | ב | ג | ד | ה | F |
|---|---|---|---|---|---|---|---|---|---|
| 1 | א | – | א | 0 | A-10 | A-15 | X-∞ | X-∞ | X-∞ |
| 2 | ב, ג | א | ב | 0 | A-10 | A-15 | B-22 | X-∞ | B-25 |
| 3 | C, F, D | A, B | ג | 0 | A-10 | A-15 | B-22 | C-25 | B-25 |
| 4 | D, E, F | א ב ג | ד | 0 | A-10 | A-15 | B-22 | D-24 | D-23 |
| 5 | E, F | א ב ג ד | F | 0 | A-10 | A-15 | B-22 | D-24 | D-23 |
| 6 | ה | A, B, C, D, F | ה | 0 | A-10 | A-15 | B-22 | D-24 | D-23 |
| סופי | – | את כל | אף אחד | 0 | A-10 | A-15 | B-22 | D-24 | D-23 |
הסימון B-22, למשל, אומר שצומת B הוא הקודם המיידי, עם מרחק כולל של 22 מצומת A.
לבסוף, אנו יכולים לחשב את הנתיבים הקצרים ביותר מצומת A הם כדלקמן:
- צומת B: A -> B (מרחק כולל = 10)
- צומת C: A -> C (מרחק כולל = 15)
- צומת D: A -> B -> D (מרחק כולל = 22)
- צומת E: A -> B -> D -> E (מרחק כולל = 24)
- צומת F: A -> B -> D -> F (מרחק כולל = 23)
3. יישום ג'אווה
ביישום פשוט זה נציג גרף כמערכת צמתים:
גרף בכיתה ציבורית {צמתים פרטיים סטים = חדש HashSet (); ריק ריק addNode (Node nodeA) {nodes.add (nodeA); } // גטרים וקובעים}ניתן לתאר צומת בעזרת a שֵׁם, א רשימה מקושרת בהתייחס ל הדרך הכי קצרה, א מֶרְחָק מהמקור, ורשימת סמיכות בשם צמתים צמודים:
ציבורי בכיתה ציבורית {שם מחרוזת פרטי; רשימה פרטית shortestPath = new LinkedList (); מרחק שלם פרטי פרטי = מספר שלם.MAX_VALUE; מיפוי שכנות צמודה = HashMap חדש (); בטל ציבורי addDestination (יעד הצומת, מרחק ה- int) {סמוךNodes.put (היעד, המרחק); } צומת ציבורי (שם מחרוזת) {this.name = שם; } // גטרים וקובעים}ה צמתים צמודים התכונה משמשת לקישור שכנים מיידיים עם אורך הקצה. זהו יישום פשוט של רשימת סמיכות, המתאימה יותר לאלגוריתם Dijkstra מאשר למטריצת הצמידות.
בנוגע ל הדרך הכי קצרה תכונה, זוהי רשימת צמתים המתארת את הנתיב הקצר ביותר המחושב מצומת ההתחלה.
כברירת מחדל, כל מרחקי הצומת מאותחל עם מספר שלם.MAX_VALUE לדמות מרחק אינסופי כמתואר בשלב האתחול.
עכשיו, בואו נשתמש באלגוריתם Dijkstra:
גרף סטטי ציבורי calculateShortestPathFromSource (גרף גרף, מקור צומת) {source.setDistance (0); הגדר settNodes = HashSet חדש (); הגדר unsettledNodes = HashSet חדש (); unsettledNodes.add (מקור); בעוד (unsettledNodes.size ()! = 0) {Node currentNode = getLowestDistanceNode (unsettledNodes); unsettledNodes.remove (currentNode); עבור (כניסה adjacencyPair: currentNode.getAdjacentNodes (). entrySet ()) {צומת naastNode = adjacencyPair.getKey (); שלם edgeWeight = adjacencyPair.getValue (); if (! SettNodes.contains (neighbouringNode)) {calcinMinimumDistance (neighbouringNode, edgeWeight, currentNode); unsettledNodes.add (סמוך לצומת); }} settNodes.add (currentNode); } גרף החזרה; }ה getLowestDistanceNode () שיטה, מחזירה את הצומת עם המרחק הנמוך ביותר מהקבוצת הצמתים הלא מסודרים, ואילו ה- חישוב מינימום מרחק () השיטה משווה את המרחק האמיתי לזו המחושבת בזמן שעוברת אחר הנתיב שנחקר לאחרונה:
צומת סטטית פרטית getLowestDistanceNode (הגדר צמתים לא מסודרים) {Node lowerDistanceNode = null; int הנמוך ביותר Distance = Integer.MAX_VALUE; עבור (צומת צומת: unsettledNodes) {int nodeDistance = node.getDistance (); אם (nodeDistance <leechDistance) {lowDistance = nodeDistance; LowDistanceNode = צומת; }} להחזיר lowDistanceNode; }חלל סטטי פרטי CalculateMinimumDistance (EvaluationNode של הצומת, edgeWeigh שלם, צומת sourceNode) {SourceTistance שלם = sourceNode.getDistance (); אם (sourceDistance + edgeWeigh <valuationNode.getDistance ()) {valuationNode.setDistance (sourceDistance + edgeWeigh); LinkedList shortestPath = חדש LinkedList (sourceNode.getShortestPath ()); shortestPath.add (sourceNode); assessmentNode.setShortestPath (shortestPath); }}עכשיו כשכל החלקים הדרושים נמצאים במקום, בואו נשתמש באלגוריתם Dijkstra על גרף הדוגמה הנושא של המאמר:
צומת nodeA = צומת חדש ("A"); צומת nodeB = צומת חדש ("B"); צומת nodeC = צומת חדש ("C"); צומת nodeD = צומת חדש ("D"); צומת nodeE = צומת חדש ("E"); צומת nodeF = צומת חדש ("F"); nodeA.addDestination (nodeB, 10); nodeA.addDestination (nodeC, 15); nodeB.addDestination (nodeD, 12); nodeB.addDestination (nodeF, 15); nodeC.addDestination (nodeE, 10); nodeD.addDestination (nodeE, 2); nodeD.addDestination (nodeF, 1); nodeF.addDestination (nodeE, 5); גרף גרף = גרף חדש (); graph.addNode (nodeA); graph.addNode (nodeB); graph.addNode (nodeC); graph.addNode (nodeD); graph.addNode (nodeE); graph.addNode (nodeF); גרף = Dijkstra.calculateShortestPathFromSource (גרף, nodeA); לאחר החישוב, הדרך הכי קצרה ו מֶרְחָק תכונות מוגדרות עבור כל צומת בגרף, אנו יכולים לחזור באמצעותן כדי לוודא שהתוצאות תואמות בדיוק את מה שנמצא בסעיף הקודם.
4. מסקנה
במאמר זה ראינו כיצד האלגוריתם Dijkstra פותר את ה- SPP וכיצד ליישם אותו ב- Java.
היישום של פרויקט פשוט זה נמצא בקישור הפרויקט הבא של GitHub.
