המדריך הבא ילמד אותנו על אלגוריתם הנתיב הקצר ביותר של דיקסטרה. נבין את פעולת האלגוריתם של דיקסטרה עם הסבר גרפי בדרגה.
אנו נכסה את הדברים הבאים:
- סקירה קצרה של מושגי היסוד של גרף
- הבן את השימוש באלגוריתם של דיקסטרה
- הבן את פעולת האלגוריתם בעזרת דוגמה שלב אחר שלב
אז בואו נתחיל.
מבוא קצר לגרפים
גרפים הם מבני נתונים לא לינאריים המייצגים את ה'חיבורים' בין האלמנטים. אלמנטים אלה ידועים בשם קודקודים , והקווים או הקשתות המחברים כל שני קודקודים בגרף ידועים בשם קצוות . באופן רשמי יותר, גרף כולל קבוצה של קודקודים (V) ו סט של קצוות (E) . הגרף מסומן על ידי G(V, E) .
רכיבי גרף
האיור הבא מציג ייצוג גרפי של גרף:
בקרת תוכנית מאוחסנת
איור 1: ייצוג גרפי של גרף
באיור לעיל, הקודקודים/הצמתים מסומנים במעגלים צבעוניים, והקצוות מסומנים עם הקווים המחברים את הצמתים.
יישומים של הגרפים
גרפים משמשים לפתרון בעיות רבות מהחיים האמיתיים. גרפים משמשים כדי לייצג את הרשתות. רשתות אלו עשויות לכלול רשתות טלפון או מעגלים או נתיבים בעיר.
לדוגמה, נוכל להשתמש בגרפים כדי לעצב מודל רשת תחבורה שבו הקודקודים מציגים את המתקנים ששולחים או מקבלים את המוצרים, והקצוות מייצגים כבישים או שבילים המחברים ביניהם. להלן ייצוג ציורי של אותו הדבר:
איור 2: ייצוג ציורי של רשת תחבורה
גרפים משמשים גם בפלטפורמות שונות של מדיה חברתית כמו לינקדאין, פייסבוק, טוויטר ועוד. לדוגמה, פלטפורמות כמו פייסבוק משתמשות בגרפים כדי לאחסן את הנתונים של המשתמשים שלהן כאשר כל אדם מסומן עם קודקוד, וכל אחד מהם הוא מבנה המכיל מידע כמו מזהה אדם, שם, מין, כתובת וכו'.
סוגי גרפים
ניתן לסווג את הגרפים לשני סוגים:
- גרף לא מכוון
- גרף בימוי
גרף לא מכוון: גרף עם קצוות שאין להם כיוון נקרא גרף לא מכוון. הקצוות של גרף זה מרמזים על קשר דו-כיווני שבו ניתן לחצות כל קצה בשני הכיוונים. האיור הבא מציג גרף פשוט לא מכוון עם ארבעה צמתים וחמישה קצוות.
איור 3: גרף פשוט לא מכוון
גרף בימוי: גרף עם קצוות עם כיוון נקרא גרף מכוון. הקצוות של גרף זה מרמזים על קשר חד-כיווני שבו ניתן לחצות כל קצה רק בכיוון אחד. האיור הבא מציג גרף מכוון פשוט עם ארבעה צמתים וחמישה קצוות.
איור 4: גרף מכוון פשוט
לאורך, למיקום או לכיוון המוחלט של הקצוות באיור גרף אין משמעות אופיינית. במילים אחרות, אנו יכולים לדמיין את אותו הגרף בדרכים שונות על ידי סידור מחדש של הקודקודים או עיוות הקצוות אם המבנה הבסיסי של הגרף אינו משתנה.
מהם גרפים משוקללים?
אומרים שגרף משוקלל אם לכל קצה מוקצה 'משקל'. משקלו של קצה יכול להצביע על מרחק, זמן או כל דבר שמדגים את ה'חיבור' בין צמד הקודקודים שהוא מחבר.
לדוגמה, אנו יכולים לראות מספר כחול ליד כל קצה באיור הבא של הגרף המשוקלל. מספר זה משמש כדי לסמן את המשקל של הקצה המתאים.
איור 5: דוגמה של גרף משוקלל
מבוא לאלגוריתם של דיקסטרה
עכשיו כשאנחנו מכירים כמה מושגי גרפים בסיסיים, בואו נצלול להבנת המושג האלגוריתם של דיקסטרה.
תהיתם פעם איך מפות גוגל מוצאת את המסלול הקצר והמהיר ביותר בין שני מקומות?
ובכן, התשובה היא האלגוריתם של דיקסטרה . האלגוריתם של דיקסטרה הוא אלגוריתם גרף שמוצא את הדרך הקצרה ביותר מקודקוד מקור לכל שאר הקודקודים בגרף (הנתיב הקצר ביותר של מקור יחיד). זהו סוג של אלגוריתם חמדן שפועל רק על גרפים משוקללים בעלי משקלים חיוביים. מורכבות הזמן של האלגוריתם של דיקסטרה היא O(V2) בעזרת ייצוג מטריצת הסמיכות של הגרף. הזמן הזה ניתן לצמצם את המורכבות O((V + E) log V) בעזרת ייצוג רשימת סמיכות של הגרף, איפה IN הוא מספר הקודקודים ו ו הוא מספר הקצוות בגרף.
היסטוריה של האלגוריתם של דיקסטרה
האלגוריתם של דיקסטרה תוכנן ופורסם על ידי ד'ר. Edsger W. Dijkstra , מדען מחשבים, מהנדס תוכנה, מתכנת, מסאי מדעי ומדען מערכות הולנדי.
חבילת כלי קפיץ
במהלך ראיון עם פיליפ ל. פראנה לתקשורת של כתב העת ACM בשנת 2001, ד'ר אדסגר וו. דיקסטרה חשף:
'מהי הדרך הקצרה ביותר לנסוע מרוטרדם לחרונינגן, באופן כללי: מעיר נתון לעיר נתונה? זהו האלגוריתם לנתיב הקצר ביותר, שתכננתי תוך כעשרים דקות. בוקר אחד עשיתי קניות באמסטרדם עם ארוסתי הצעירה, ועייפים, התיישבנו על מרפסת בית הקפה לשתות כוס קפה ורק חשבתי אם אני יכול לעשות את זה, ואז תכננתי את האלגוריתם לדרך הקצרה ביותר. . כפי שאמרתי, זו הייתה המצאה של עשרים דקות. למעשה, הוא פורסם ב-59', שלוש שנים לאחר מכן. הפרסום עדיין קריא, הוא, למעשה, די נחמד. אחת הסיבות שהוא כל כך נחמד הייתה שעיצבתי אותו בלי עיפרון ונייר. למדתי מאוחר יותר שאחד היתרונות של עיצוב ללא עיפרון ונייר הוא שאתה כמעט נאלץ להימנע מכל המורכבויות הניתנות להימנעות. בסופו של דבר, האלגוריתם הזה הפך לתדהמתי הרבה, לאחת מאבני היסוד של התהילה שלי״.
דיקסטרה חשב על בעיית הדרך הקצרה ביותר בזמן שעבד כמתכנת במרכז המתמטי באמסטרדם בשנת 1956 כדי להמחיש את היכולות של מחשב חדש המכונה ARMAC. המטרה שלו הייתה לבחור גם בעיה וגם פתרון (שיוצר על ידי המחשב) שאנשים ללא רקע מחשב יכלו להבין. הוא פיתח את אלגוריתם הנתיב הקצר ביותר ומאוחר יותר ביצע אותו עבור ARMAC עבור מפת תחבורה מקוצרת במעורפל של 64 ערים בהולנד (64 ערים, כך ש-6 סיביות יספיקו כדי לקודד את מספר העיר). שנה לאחר מכן, הוא נתקל בבעיה נוספת של מהנדסי חומרה המפעילים את המחשב הבא של המכון: צמצמו למינימום את כמות החוט הנדרשת לחיבור הפינים בלוח האחורי של המכונה. כפתרון, הוא גילה מחדש את האלגוריתם שנקרא Prim's minimal spaning tree algorithm ופרסם אותו בשנת 1959.
יסודות האלגוריתם של דיקסטרה
להלן המושגים הבסיסיים של האלגוריתם של דיקסטרה:
- האלגוריתם של דיקסטרה מתחיל בצומת שאנו בוחרים (צומת המקור), והוא בוחן את הגרף כדי למצוא את הנתיב הקצר ביותר בין הצומת הזה לכל שאר הצמתים בגרף.
- האלגוריתם שומר תיעוד של המרחק הקצר ביותר המאושר כעת מכל צומת לצומת המקור, והוא מעדכן את הערכים הללו אם הוא מוצא נתיב קצר יותר.
- לאחר שהאלגוריתם אחזר את הנתיב הקצר ביותר בין המקור לצומת אחר, הצומת הזה מסומן כ'ביקר' ונכלל בנתיב.
- ההליך ממשיך עד שכל הצמתים בגרף נכללים בנתיב. באופן זה, יש לנו נתיב המחבר את צומת המקור לכל הצמתים האחרים, עוקב אחר הנתיב הקצר ביותר כדי להגיע לכל צומת.
הבנת פעולת האלגוריתם של דיקסטרה
א גרָף ו קודקוד מקור הן דרישות עבור האלגוריתם של דיקסטרה. אלגוריתם זה מבוסס על Greedy Approach ובכך מוצא את הבחירה האופטימלית המקומית (מינימום מקומי במקרה זה) בכל שלב באלגוריתם.
לכל קודקוד באלגוריתם זה יוגדרו שני מאפיינים עבורו:
- ביקר בנכס
- נכס נתיב
הבה נבין את המאפיינים הללו בקצרה.
נכס ביקר:
- המאפיין 'ביקר' מציין אם הצומת ביקר או לא.
- אנו משתמשים במאפיין זה כדי שלא נבקר שוב באף צומת.
- צומת מסומן כביקור רק כאשר נמצא הנתיב הקצר ביותר.
נכס נתיב:
- המאפיין 'נתיב' מאחסן את הערך של הנתיב המינימלי הנוכחי לצומת.
- נתיב המינימום הנוכחי מרמז על הדרך הקצרה ביותר שהגענו לצומת זה עד כה.
- מאפיין זה מתוקן כאשר מבקרים כל שכן של הצומת.
- מאפיין זה משמעותי מכיוון שהוא יאחסן את התשובה הסופית עבור כל צומת.
בתחילה, אנו מסמנים את כל הקודקודים, או הצמתים, שלא ביקרו בהם מכיוון שטרם ביקרו בהם. גם הנתיב לכל הצמתים מוגדר לאינסוף מלבד צומת המקור. יתר על כן, הנתיב לצומת המקור מוגדר לאפס (0).
לאחר מכן נבחר את צומת המקור ונסמן אותו כביקור. לאחר מכן, אנו ניגשים לכל הצמתים הסמוכים של צומת המקור ומבצעים הרפיה בכל צומת. הרפיה היא תהליך של הורדת עלות ההגעה לצומת בעזרת צומת אחר.
בתהליך הרפיה, הנתיב של כל צומת מתוקן לערך המינימלי בין הנתיב הנוכחי של הצומת, סכום הנתיב לצומת הקודם והנתיב מהצומת הקודם לצומת הנוכחי.
נניח ש-p[n] הוא הערך של הנתיב הנוכחי עבור צומת n, p[m] הוא הערך של הנתיב עד לצומת שביקרתם בעבר, ו-w הוא משקל הקצה בין הצומת הנוכחי לצומת. ביקר בעבר באחד (משקל קצה בין n ל-m).
במובן המתמטי, ניתן להמחיש הרפיה כ:
p[n] = מינימום(p[n], p[m] + w)
לאחר מכן, אנו מסמנים צומת שלא ביקר עם הנתיב הנמוך ביותר כפי שביקר בו בכל שלב שלאחר מכן, ומעדכנים את הנתיבים של שכנו.
אנו חוזרים על הליך זה עד שכל הצמתים בגרף מסומנים כביקורים.
בכל פעם שאנו מוסיפים צומת לקבוצה שבה ביקר, גם הנתיב לכל הצמתים השכנים שלו משתנה בהתאם.
גיזום אלפא ביתא
אם צומת כלשהו נותר בלתי ניתן להשגה (רכיב מנותק), הנתיב שלו נשאר 'אינסוף'. במקרה שהמקור עצמו הוא רכיב נפרד, הנתיב לכל שאר הצמתים נשאר 'אינסוף'.
הבנת האלגוריתם של דיקסטרה עם דוגמה
להלן הצעד שנבצע כדי ליישם את האלגוריתם של דיקסטרה:
שלב 1: ראשית, נסמן את צומת המקור במרחק נוכחי של 0 ונקבע את שאר הצמתים ל-INFINITY.
שלב 2: לאחר מכן נגדיר את הצומת שלא ביקר עם מרחק הזרם הקטן ביותר כצומת הנוכחי, נניח X.
שלב 3: עבור כל שכן N של הצומת הנוכחי X: לאחר מכן נוסיף את המרחק הנוכחי של X עם משקל הקצה המצטרף X-N. אם הוא קטן מהמרחק הנוכחי של N, הגדר אותו כמרחק הנוכחי החדש של N.
שלב 4: לאחר מכן נסמן את הצומת הנוכחי X כביקור בו.
שלב 5: נחזור על התהליך מ 'שלב 2' אם ישנו צומת שלא ביקר בגרף.
הבה נבין כעת את יישום האלגוריתם בעזרת דוגמה:
איור 6: הגרף הנתון
- נשתמש בגרף שלמעלה כקלט, עם צומת א בתור המקור.
- ראשית, נסמן את כל הצמתים כלא ביקרו.
- אנחנו נקבע את הדרך ל 0 בצומת א ו אינסוף עבור כל שאר הצמתים.
- כעת נסמן צומת מקור א כפי שביקר וגישה לצמתים השכנים שלו.
הערה: ניגשנו רק לצמתים הסמוכים, לא ביקרנו בהם. - כעת נעדכן את הנתיב לצומת ב על ידי 4 בעזרת הרפיה כי הדרך לצומת א הוא 0 והנתיב מהצומת א ל ב הוא 4 , וה מינימום((0 + 4), אינסוף) הוא 4 .
- אנו גם נעדכן את הנתיב לצומת ג על ידי 5 בעזרת הרפיה כי הדרך לצומת א הוא 0 והנתיב מהצומת א ל ג הוא 5 , וה מינימום((0 + 5), אינסוף) הוא 5 . שני השכנים של צומת א כעת רגועים; לכן, אנחנו יכולים להתקדם.
- כעת נבחר את הצומת הלא ביקר הבא עם הכי פחות נתיב ונבקר בו. לפיכך, נבקר בצומת ב ולבצע הרפיה על שכניו הלא ביקרו. לאחר ביצוע הרפיה, הדרך לצומת ג יישאר 5 , ואילו הנתיב לצומת ו יהפוך אחד עשר , והנתיב לצומת ד יהפוך 13 .
- כעת נבקר בצומת ו ולבצע הרפיה בצמתים הסמוכים לו ב, ד , ו ו . מאז רק צומת ו לא ביקר, זה יהיה רגוע. לפיכך, הדרך לצומת ב יישאר כפי שהוא, כלומר, 4 , הנתיב לצומת ד גם יישאר 13 , והנתיב לצומת ו יהפוך 14 (8 + 6) .
- כעת נבקר בצומת ד , ורק צומת ו יהיה רגוע. עם זאת, הנתיב לצומת ו יישאר ללא שינוי, כלומר, 14 .
- מאז רק צומת ו נשאר, נבקר בו אך לא נבצע הרפיה מכיוון שכל הצמתים השכנים שלו כבר ביקרו.
- לאחר ביקור בכל הצמתים של הגרפים, התוכנית תסתיים.
לפיכך, הנתיבים האחרונים שסיכמנו הם:
A = 0 B = 4 (A -> B) C = 5 (A -> C) D = 4 + 9 = 13 (A -> B -> D) E = 5 + 3 = 8 (A -> C -> E) F = 5 + 3 + 6 = 14 (A -> C -> E -> F)
פסאודוקוד עבור האלגוריתם של דיקסטרה
כעת נבין פסאודוקוד עבור האלגוריתם של דיקסטרה.
- עלינו לשמור תיעוד של מרחק הנתיב של כל צומת. לכן, אנו יכולים לאחסן את מרחק הנתיב של כל צומת במערך בגודל n, כאשר n הוא המספר הכולל של צמתים.
- יתר על כן, אנו רוצים לאחזר את הנתיב הקצר ביותר יחד עם אורך הנתיב הזה. כדי להתגבר על בעיה זו, נמפה כל צומת לצומת שעדכן לאחרונה את אורך הנתיב שלו.
- לאחר השלמת האלגוריתם, נוכל לעקוב אחר צומת היעד לצומת המקור כדי לאחזר את הנתיב.
- אנו יכולים להשתמש בתור עדיפות מינימלית כדי לאחזר את הצומת עם מרחק הנתיב הקטן ביותר בצורה יעילה.
הבה ניישם כעת פסאודוקוד של האיור לעיל:
פסאודוקוד:
function Dijkstra_Algorithm(Graph, source_node) // iterating through the nodes in Graph and set their distances to INFINITY for each node N in Graph: distance[N] = INFINITY previous[N] = NULL If N != source_node, add N to Priority Queue G // setting the distance of the source node of the Graph to 0 distance[source_node] = 0 // iterating until the Priority Queue G is not empty while G is NOT empty: // selecting a node Q having the least distance and marking it as visited Q = node in G with the least distance[] mark Q visited // iterating through the unvisited neighboring nodes of the node Q and performing relaxation accordingly for each unvisited neighbor node N of Q: temporary_distance = distance[Q] + distance_between(Q, N) // if the temporary distance is less than the given distance of the path to the Node, updating the resultant distance with the minimum value if temporary_distance <distance[n] distance[n] :="temporary_distance" previous[n] returning the final list of distance return distance[], previous[] < pre> <p> <strong>Explanation:</strong> </p> <p>In the above pseudocode, we have defined a function that accepts multiple parameters - the Graph consisting of the nodes and the source node. Inside this function, we have iterated through each node in the Graph, set their initial distance to <strong>INFINITY</strong> , and set the previous node value to <strong>NULL</strong> . We have also checked whether any selected node is not a source node and added the same into the Priority Queue. Moreover, we have set the distance of the source node to <strong>0</strong> . We then iterated through the nodes in the priority queue, selected the node with the least distance, and marked it as visited. We then iterated through the unvisited neighboring nodes of the selected node and performed relaxation accordingly. At last, we have compared both the distances (original and temporary distance) between the source node and the destination node, updated the resultant distance with the minimum value and previous node information, and returned the final list of distances with their previous node information.</p> <h2>Implementation of Dijkstra's Algorithm in Different Programming Languages</h2> <p>Now that we have successfully understood the pseudocode of Dijkstra's Algorithm, it is time to see its implementation in different programming languages like C, C++, Java, and Python.</p> <h3>Code for Dijkstra's Algorithm in C</h3> <p>The following is the implementation of Dijkstra's Algorithm in the C Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.c</strong> </p> <pre> // Implementation of Dijkstra's Algorithm in C // importing the standard I/O header file #include // defining some constants #define INF 9999 #define MAX 10 // prototyping of the function void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start); // defining the function for Dijkstra's Algorithm void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start) { int cost[MAX][MAX], distance[MAX], previous[MAX]; int visited_nodes[MAX], counter, minimum_distance, next_node, i, j; // creating cost matrix for (i = 0; i <size; i++) for (j="0;" j < size; j++) if (graph[i][j]="=" 0) cost[i][j]="INF;" else (i="0;" i { distance[i]="cost[start][i];" previous[i]="start;" visited_nodes[i]="0;" } distance[start]="0;" visited_nodes[start]="1;" counter="1;" while (counter size - 1) minimum_distance="INF;" (distance[i] && !visited_nodes[i]) next_node="i;" visited_nodes[next_node]="1;" (!visited_nodes[i]) (minimum_distance + cost[next_node][i] distance[i]) cost[next_node][i]; counter++; printing the distance !="start)" printf('
distance from source node to %d: %d', i, distance[i]); main function int main() defining variables graph[max][max], j, size, source; declaring of matrix nodes graph graph[0][0]="0;" graph[0][1]="4;" graph[0][2]="0;" graph[0][3]="0;" graph[0][4]="0;" graph[0][5]="8;" graph[0][6]="0;" graph[1][0]="4;" graph[1][1]="0;" graph[1][2]="8;" graph[1][3]="0;" graph[1][4]="0;" graph[1][5]="11;" graph[1][6]="0;" graph[2][0]="0;" graph[2][1]="8;" graph[2][2]="0;" graph[2][3]="7;" graph[2][4]="0;" graph[2][5]="4;" graph[2][6]="0;" graph[3][0]="0;" graph[3][1]="0;" graph[3][2]="7;" graph[3][3]="0;" graph[3][4]="9;" graph[3][5]="14;" graph[3][6]="0;" graph[4][0]="0;" graph[4][1]="0;" graph[4][2]="0;" graph[4][3]="9;" graph[4][4]="0;" graph[4][5]="10;" graph[4][6]="2;" graph[5][0]="0;" graph[5][1]="0;" graph[5][2]="4;" graph[5][3]="14;" graph[5][4]="10;" graph[5][5]="0;" graph[5][6]="2;" graph[6][0]="0;" graph[6][1]="0;" graph[6][2]="0;" graph[6][3]="0;" graph[6][4]="2;" graph[6][5]="0;" graph[6][6]="1;" calling dijkstraalgorithm() by passing graph, number and dijkstraalgorithm(graph, source); return 0; pre> <p> <strong>Output</strong> </p> <pre> Distance from the Source Node to 1: 4 Distance from the Source Node to 2: 12 Distance from the Source Node to 3: 19 Distance from the Source Node to 4: 12 Distance from the Source Node to 5: 8 Distance from the Source Node to 6: 10 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have included the <strong>stdio.h</strong> header file defined two constant values: <strong>INF = 9999</strong> and <strong>MAX = 10</strong> . We have declared the prototyping of the function and then defined the function for Dijkstra's Algorithm as <strong>DijkstraAlgorithm</strong> that accepts three arguments - the Graph consisting of the nodes, the number of nodes in the Graph, and the source node. Inside this function, we have defined some data structures such as a 2D matrix that will work as the Priority Queue for the algorithm, an array to main the distance between the nodes, an array to maintain the record of previous nodes, an array to store the visited nodes information, and some integer variables to store minimum distance value, counter, next node value and more. We then used a <strong>nested for-loop</strong> to iterate through the nodes of the Graph and add them to the priority queue accordingly. We have again used the <strong>for-loop</strong> to iterate through the elements in the priority queue starting from the source node and update their distances. Outside the loop, we have set the distance of the source node as <strong>0</strong> and marked it as visited in the <strong>visited_nodes[]</strong> array. We then set the counter value as one and used the <strong>while</strong> loop iterating through the number of nodes. Inside this loop, we have set the value of <strong>minimum_distance</strong> as <strong>INF</strong> and used the <strong>for-loop</strong> to update the value of the <strong>minimum_distance</strong> variable with the minimum value from a <strong>distance[]</strong> array. We then iterated through the unvisited neighboring nodes of the selected node using the <strong>for-loop</strong> and performed relaxation. We then printed the resulting data of the distances calculated using Dijkstra's Algorithm.</p> <p>In the <strong>main</strong> function, we have defined and declared the variables representing the Graph, the number of nodes, and the source node. At last, we have called the <strong>DijkstraAlgorithm()</strong> function by passing the required parameters.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra's Algorithm in C++</h3> <p>The following is the implementation of Dijkstra's Algorithm in the C++ Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.cpp</strong> </p> <pre> // Implementation of Dijkstra's Algorithm in C++ // importing the required header files #include #include // defining constant #define MAX_INT 10000000 // using the standard namespace using namespace std; // prototyping of the DijkstraAlgorithm() function void DijkstraAlgorithm(); // main function int main() { DijkstraAlgorithm(); return 0; } // declaring the classes class Vertex; class Edge; // prototyping the functions void Dijkstra(); vector* Adjacent_Remaining_Nodes(Vertex* vertex); Vertex* Extract_Smallest(vector& vertices); int Distance(Vertex* vertexOne, Vertex* vertexTwo); bool Contains(vector& vertices, Vertex* vertex); void Print_Shortest_Route_To(Vertex* des); // instantiating the classes vector vertices; vector edges; // defining the class for the vertices of the graph class Vertex { public: Vertex(char id) : id(id), prev(NULL), distance_from_start(MAX_INT) { vertices.push_back(this); } public: char id; Vertex* prev; int distance_from_start; }; // defining the class for the edges of the graph class Edge { public: Edge(Vertex* vertexOne, Vertex* vertexTwo, int distance) : vertexOne(vertexOne), vertexTwo(vertexTwo), distance(distance) { edges.push_back(this); } bool Connects(Vertex* vertexOne, Vertex* vertexTwo) public: Vertex* vertexOne; Vertex* vertexTwo; int distance; }; // defining the function to collect the details of the graph void DijkstraAlgorithm() { // declaring some vertices Vertex* vertex_a = new Vertex('A'); Vertex* vertex_b = new Vertex('B'); Vertex* vertex_c = new Vertex('C'); Vertex* vertex_d = new Vertex('D'); Vertex* vertex_e = new Vertex('E'); Vertex* vertex_f = new Vertex('F'); Vertex* vertex_g = new Vertex('G'); // declaring some edges Edge* edge_1 = new Edge(vertex_a, vertex_c, 1); Edge* edge_2 = new Edge(vertex_a, vertex_d, 2); Edge* edge_3 = new Edge(vertex_b, vertex_c, 2); Edge* edge_4 = new Edge(vertex_c, vertex_d, 1); Edge* edge_5 = new Edge(vertex_b, vertex_f, 3); Edge* edge_6 = new Edge(vertex_c, vertex_e, 3); Edge* edge_7 = new Edge(vertex_e, vertex_f, 2); Edge* edge_8 = new Edge(vertex_d, vertex_g, 1); Edge* edge_9 = new Edge(vertex_g, vertex_f, 1); vertex_a -> distance_from_start = 0; // setting a start vertex // calling the Dijkstra() function to find the shortest route possible Dijkstra(); // calling the Print_Shortest_Route_To() function to print the shortest route from the source vertex to the destination vertex Print_Shortest_Route_To(vertex_f); } // defining the function for Dijkstra's Algorithm void Dijkstra() { while (vertices.size() > 0) { Vertex* smallest = Extract_Smallest(vertices); vector* adjacent_nodes = Adjacent_Remaining_Nodes(smallest); const int size = adjacent_nodes -> size(); for (int i = 0; i at(i); int distance = Distance(smallest, adjacent) + smallest -> distance_from_start; if (distance distance_from_start) { adjacent -> distance_from_start = distance; adjacent -> prev = smallest; } } delete adjacent_nodes; } } // defining the function to find the vertex with the shortest distance, removing it, and returning it Vertex* Extract_Smallest(vector& vertices) { int size = vertices.size(); if (size == 0) return NULL; int smallest_position = 0; Vertex* smallest = vertices.at(0); for (int i = 1; i distance_from_start distance_from_start) { smallest = current; smallest_position = i; } } vertices.erase(vertices.begin() + smallest_position); return smallest; } // defining the function to return all vertices adjacent to 'vertex' which are still in the 'vertices' collection. vector* Adjacent_Remaining_Nodes(Vertex* vertex) { vector* adjacent_nodes = new vector(); const int size = edges.size(); for (int i = 0; i vertexOne == vertex) { adjacent = edge -> vertexTwo; } else if (edge -> vertexTwo == vertex) { adjacent = edge -> vertexOne; } if (adjacent && Contains(vertices, adjacent)) { adjacent_nodes -> push_back(adjacent); } } return adjacent_nodes; } // defining the function to return distance between two connected vertices int Distance(Vertex* vertexOne, Vertex* vertexTwo) { const int size = edges.size(); for (int i = 0; i Connects(vertexOne, vertexTwo)) { return edge -> distance; } } return -1; // should never happen } // defining the function to check if the 'vertices' vector contains 'vertex' bool Contains(vector& vertices, Vertex* vertex) { const int size = vertices.size(); for (int i = 0; i <size; ++i) { if (vertex="=" vertices.at(i)) return true; } false; defining the function to print shortest route destination void print_shortest_route_to(vertex* des) vertex* prev="des;" cout << 'distance from start: ' < distance_from_start endl; while (prev) id prev; pre> <p> <strong>Output</strong> </p> <pre> Distance from start: 4 F G D A </pre> <p> <strong>Explanation:</strong> </p> <p>In the above code snippet, we included the <strong>'iostream'</strong> and <strong>'vector'</strong> header files and defined a constant value as <strong>MAX_INT = 10000000</strong> . We then used the standard namespace and prototyped the <strong>DijkstraAlgorithm()</strong> function. We then defined the main function of the program within, which we have called the <strong>DijkstraAlgorithm()</strong> function. After that, we declared some classes to create vertices and edges. We have also prototyped more functions to find the shortest possible path from the source vertex to the destination vertex and instantiated the Vertex and Edge classes. We then defined both classes to create the vertices and edges of the graph. We have then defined the <strong>DijkstraAlgorithm()</strong> function to create a graph and perform different operations. Inside this function, we have declared some vertices and edges. We then set the source vertex of the graph and called the <strong>Dijkstra()</strong> function to find the shortest possible distance and <strong>Print_Shortest_Route_To()</strong> function to print the shortest distance from the source vertex to vertex <strong>'F'</strong> . We have then defined the <strong>Dijkstra()</strong> function to calculate the shortest possible distances of the all the vertices from the source vertex. We have also defined some more functions to find the vertex with the shortest distance to return all the vertices adjacent to the remaining vertex, to return the distance between two connected vertices, to check if the selected vertex exists in the graph, and to print the shortest possible path from the source vertex to the destination vertex.</p> <p>As a result, the required shortest path for the vertex <strong>'F'</strong> from the source node is printed for the users.</p> <h3>Code for Dijkstra's Algorithm in Java</h3> <p>The following is the implementation of Dijkstra's Algorithm in the Java Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.java</strong> </p> <pre> // Implementation of Dijkstra's Algorithm in Java // defining the public class for Dijkstra's Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra's Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format('distance from %s to %s', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra's Algorithm in Python</h3> <p>The following is the implementation of Dijkstra's Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra's Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print('Distance of', chr(ord('A') + i), 'from source node:', distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra's Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra's Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra's Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra's Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra's Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra's Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra's algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra's Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra's Algorithm</h2> <p> <strong>Dijkstra's Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra's algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra's Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra's Algorithm. The standard Dijkstra's Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra's Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, 'b'. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, 'b', is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra's Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra's Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra's Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra's Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra's Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of 'hops' from the file server to every other computer on the network, we will use Dijkstra's Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra's Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra's Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra's Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra's Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra's algorithm and some of its real-life applications.</li> </ul> <hr></nodes;></pre></size;></pre></size;></pre></distance[n]> הֶסבֵּר:
בקטע הקוד שלמעלה, כללנו את stdio.h קובץ header הגדיר שני ערכים קבועים: INF = 9999 ו MAX = 10 . הכרזנו על יצירת אב טיפוס של הפונקציה ולאחר מכן הגדרנו את הפונקציה עבור האלגוריתם של דיקסטרה כ אלגוריתם דיקסטרא שמקבל שלושה ארגומנטים - הגרף המורכב מהצמתים, מספר הצמתים בגרף וצומת המקור. בתוך פונקציה זו, הגדרנו כמה מבני נתונים כגון מטריצה דו-ממדית שתעבוד בתור Priority Queue עבור האלגוריתם, מערך לניהול המרחק בין הצמתים, מערך לשמירה על הרשומה של צמתים קודמים, מערך לאחסון מידע על הצמתים שביקרו, וכמה משתנים שלמים לאחסון ערך מרחק מינימלי, מונה, ערך הצומת הבא ועוד. לאחר מכן השתמשנו ב- a מקונן for-loop לעבור דרך הצמתים של הגרף ולהוסיף אותם לתור העדיפות בהתאם. השתמשנו שוב ב- for-loop לחזור על האלמנטים בתור העדיפות החל מצומת המקור ולעדכן את המרחקים שלהם. מחוץ ללולאה, קבענו את המרחק של צומת המקור כ 0 וסימן אותו כביקור ב- ביקורים_צמתים[] מַעֲרָך. לאחר מכן הגדרנו את ערך המונה כאחד והשתמשנו ב- בזמן לולאה חוזרת דרך מספר הצמתים. בתוך הלולאה הזו, קבענו את הערך של מינימום_מרחק כפי ש INF והשתמשו ב for-loop כדי לעדכן את הערך של מינימום_מרחק משתנה עם הערך המינימלי מ-a מֶרְחָק[] מַעֲרָך. לאחר מכן עברנו דרך הצמתים השכנים שלא ביקרו של הצומת שנבחר באמצעות ה- for-loop וביצע הרפיה. לאחר מכן הדפסנו את הנתונים המתקבלים של המרחקים שחושבו באמצעות האלגוריתם של דיקסטרה.
בתוך ה רָאשִׁי פונקציה, הגדרנו והכרזנו על המשתנים המייצגים את הגרף, מספר הצמתים וצומת המקור. סוף סוף, התקשרנו ל- DijkstraAlgorithm() לתפקד על ידי העברת הפרמטרים הנדרשים.
כתוצאה מכך, הנתיבים הקצרים ביותר הנדרשים עבור כל צומת מצומת המקור מודפסים עבור המשתמשים.
קוד עבור האלגוריתם של דיקסטרה ב-C++
להלן יישום האלגוריתם של דיקסטרה בשפת התכנות C++:
קובץ: DijkstraAlgorithm.cpp
מחרוזת רשימת java
// Implementation of Dijkstra's Algorithm in C++ // importing the required header files #include #include // defining constant #define MAX_INT 10000000 // using the standard namespace using namespace std; // prototyping of the DijkstraAlgorithm() function void DijkstraAlgorithm(); // main function int main() { DijkstraAlgorithm(); return 0; } // declaring the classes class Vertex; class Edge; // prototyping the functions void Dijkstra(); vector* Adjacent_Remaining_Nodes(Vertex* vertex); Vertex* Extract_Smallest(vector& vertices); int Distance(Vertex* vertexOne, Vertex* vertexTwo); bool Contains(vector& vertices, Vertex* vertex); void Print_Shortest_Route_To(Vertex* des); // instantiating the classes vector vertices; vector edges; // defining the class for the vertices of the graph class Vertex { public: Vertex(char id) : id(id), prev(NULL), distance_from_start(MAX_INT) { vertices.push_back(this); } public: char id; Vertex* prev; int distance_from_start; }; // defining the class for the edges of the graph class Edge { public: Edge(Vertex* vertexOne, Vertex* vertexTwo, int distance) : vertexOne(vertexOne), vertexTwo(vertexTwo), distance(distance) { edges.push_back(this); } bool Connects(Vertex* vertexOne, Vertex* vertexTwo) public: Vertex* vertexOne; Vertex* vertexTwo; int distance; }; // defining the function to collect the details of the graph void DijkstraAlgorithm() { // declaring some vertices Vertex* vertex_a = new Vertex('A'); Vertex* vertex_b = new Vertex('B'); Vertex* vertex_c = new Vertex('C'); Vertex* vertex_d = new Vertex('D'); Vertex* vertex_e = new Vertex('E'); Vertex* vertex_f = new Vertex('F'); Vertex* vertex_g = new Vertex('G'); // declaring some edges Edge* edge_1 = new Edge(vertex_a, vertex_c, 1); Edge* edge_2 = new Edge(vertex_a, vertex_d, 2); Edge* edge_3 = new Edge(vertex_b, vertex_c, 2); Edge* edge_4 = new Edge(vertex_c, vertex_d, 1); Edge* edge_5 = new Edge(vertex_b, vertex_f, 3); Edge* edge_6 = new Edge(vertex_c, vertex_e, 3); Edge* edge_7 = new Edge(vertex_e, vertex_f, 2); Edge* edge_8 = new Edge(vertex_d, vertex_g, 1); Edge* edge_9 = new Edge(vertex_g, vertex_f, 1); vertex_a -> distance_from_start = 0; // setting a start vertex // calling the Dijkstra() function to find the shortest route possible Dijkstra(); // calling the Print_Shortest_Route_To() function to print the shortest route from the source vertex to the destination vertex Print_Shortest_Route_To(vertex_f); } // defining the function for Dijkstra's Algorithm void Dijkstra() { while (vertices.size() > 0) { Vertex* smallest = Extract_Smallest(vertices); vector* adjacent_nodes = Adjacent_Remaining_Nodes(smallest); const int size = adjacent_nodes -> size(); for (int i = 0; i at(i); int distance = Distance(smallest, adjacent) + smallest -> distance_from_start; if (distance distance_from_start) { adjacent -> distance_from_start = distance; adjacent -> prev = smallest; } } delete adjacent_nodes; } } // defining the function to find the vertex with the shortest distance, removing it, and returning it Vertex* Extract_Smallest(vector& vertices) { int size = vertices.size(); if (size == 0) return NULL; int smallest_position = 0; Vertex* smallest = vertices.at(0); for (int i = 1; i distance_from_start distance_from_start) { smallest = current; smallest_position = i; } } vertices.erase(vertices.begin() + smallest_position); return smallest; } // defining the function to return all vertices adjacent to 'vertex' which are still in the 'vertices' collection. vector* Adjacent_Remaining_Nodes(Vertex* vertex) { vector* adjacent_nodes = new vector(); const int size = edges.size(); for (int i = 0; i vertexOne == vertex) { adjacent = edge -> vertexTwo; } else if (edge -> vertexTwo == vertex) { adjacent = edge -> vertexOne; } if (adjacent && Contains(vertices, adjacent)) { adjacent_nodes -> push_back(adjacent); } } return adjacent_nodes; } // defining the function to return distance between two connected vertices int Distance(Vertex* vertexOne, Vertex* vertexTwo) { const int size = edges.size(); for (int i = 0; i Connects(vertexOne, vertexTwo)) { return edge -> distance; } } return -1; // should never happen } // defining the function to check if the 'vertices' vector contains 'vertex' bool Contains(vector& vertices, Vertex* vertex) { const int size = vertices.size(); for (int i = 0; i <size; ++i) { if (vertex="=" vertices.at(i)) return true; } false; defining the function to print shortest route destination void print_shortest_route_to(vertex* des) vertex* prev="des;" cout << \'distance from start: \' < distance_from_start endl; while (prev) id prev; pre> <p> <strong>Output</strong> </p> <pre> Distance from start: 4 F G D A </pre> <p> <strong>Explanation:</strong> </p> <p>In the above code snippet, we included the <strong>'iostream'</strong> and <strong>'vector'</strong> header files and defined a constant value as <strong>MAX_INT = 10000000</strong> . We then used the standard namespace and prototyped the <strong>DijkstraAlgorithm()</strong> function. We then defined the main function of the program within, which we have called the <strong>DijkstraAlgorithm()</strong> function. After that, we declared some classes to create vertices and edges. We have also prototyped more functions to find the shortest possible path from the source vertex to the destination vertex and instantiated the Vertex and Edge classes. We then defined both classes to create the vertices and edges of the graph. We have then defined the <strong>DijkstraAlgorithm()</strong> function to create a graph and perform different operations. Inside this function, we have declared some vertices and edges. We then set the source vertex of the graph and called the <strong>Dijkstra()</strong> function to find the shortest possible distance and <strong>Print_Shortest_Route_To()</strong> function to print the shortest distance from the source vertex to vertex <strong>'F'</strong> . We have then defined the <strong>Dijkstra()</strong> function to calculate the shortest possible distances of the all the vertices from the source vertex. We have also defined some more functions to find the vertex with the shortest distance to return all the vertices adjacent to the remaining vertex, to return the distance between two connected vertices, to check if the selected vertex exists in the graph, and to print the shortest possible path from the source vertex to the destination vertex.</p> <p>As a result, the required shortest path for the vertex <strong>'F'</strong> from the source node is printed for the users.</p> <h3>Code for Dijkstra's Algorithm in Java</h3> <p>The following is the implementation of Dijkstra's Algorithm in the Java Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.java</strong> </p> <pre> // Implementation of Dijkstra's Algorithm in Java // defining the public class for Dijkstra's Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra's Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format(\'distance from %s to %s\', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra's Algorithm in Python</h3> <p>The following is the implementation of Dijkstra's Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra's Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print('Distance of', chr(ord('A') + i), 'from source node:', distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra's Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra's Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra's Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra's Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra's Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra's Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra's algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra's Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra's Algorithm</h2> <p> <strong>Dijkstra's Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra's algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra's Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra's Algorithm. The standard Dijkstra's Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra's Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, 'b'. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, 'b', is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra's Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra's Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra's Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra's Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra's Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of 'hops' from the file server to every other computer on the network, we will use Dijkstra's Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra's Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra's Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra's Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra's Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra's algorithm and some of its real-life applications.</li> </ul> <hr></nodes;></pre></size;> הֶסבֵּר:
בקטע הקוד לעיל, כללנו את 'iostream' ו 'וֶקטוֹר' קבצי header והגדיר ערך קבוע כ MAX_INT = 10000000 . לאחר מכן השתמשנו במרחב השמות הסטנדרטי ויצרנו אב טיפוס של DijkstraAlgorithm() פוּנקצִיָה. לאחר מכן הגדרנו את הפונקציה העיקרית של התוכנית שבתוכה, אותה קראנו DijkstraAlgorithm() פוּנקצִיָה. לאחר מכן, הכרזנו על כמה מחלקות ליצור קודקודים וקצוות. יצרנו גם אב טיפוס של פונקציות נוספות כדי למצוא את הנתיב הקצר ביותר האפשרי מקודקוד המקור לקודקוד היעד ויצרנו את המחלקות Vertex ו-Edge. לאחר מכן הגדרנו את שתי המחלקות כדי ליצור את הקודקודים והקצוות של הגרף. לאחר מכן הגדרנו את DijkstraAlgorithm() פונקציה ליצירת גרף ולבצע פעולות שונות. בתוך הפונקציה הזו, הכרזנו על כמה קודקודים וקצוות. לאחר מכן הגדרנו את קודקוד המקור של הגרף וקראנו את דיקסטרה() פונקציה כדי למצוא את המרחק הקצר ביותר האפשרי ו Print_Shortest_Route_To() פונקציה להדפיס את המרחק הקצר ביותר מקודקוד המקור לקודקוד 'F' . לאחר מכן הגדרנו את דיקסטרה() פונקציה לחשב את המרחקים הקצרים ביותר האפשריים של כל הקודקודים מקודקוד המקור. כמו כן, הגדרנו עוד כמה פונקציות למצוא את הקודקוד בעל המרחק הקצר ביותר כדי להחזיר את כל הקודקודים הסמוכים לקודקוד הנותר, להחזיר את המרחק בין שני קודקודים מחוברים, לבדוק אם הקודקוד שנבחר קיים בגרף, ולהדפיס את הנתיב הקצר ביותר האפשרי מקודקוד המקור לקודקוד היעד.
כתוצאה מכך, הנתיב הקצר ביותר הנדרש עבור הקודקוד 'F' מצומת המקור מודפס עבור המשתמשים.
קוד לאלגוריתם של דיקסטרה בג'אווה
להלן יישום האלגוריתם של דיקסטרה בשפת התכנות Java:
קובץ: DijkstraAlgorithm.java
// Implementation of Dijkstra's Algorithm in Java // defining the public class for Dijkstra's Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra's Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format(\'distance from %s to %s\', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra's Algorithm in Python</h3> <p>The following is the implementation of Dijkstra's Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra's Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print('Distance of', chr(ord('A') + i), 'from source node:', distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra's Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra's Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra's Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra's Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra's Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra's Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra's algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra's Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra's Algorithm</h2> <p> <strong>Dijkstra's Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra's algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra's Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra's Algorithm. The standard Dijkstra's Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra's Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, 'b'. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, 'b', is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra's Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra's Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra's Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra's Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra's Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of 'hops' from the file server to every other computer on the network, we will use Dijkstra's Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra's Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra's Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra's Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra's Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra's algorithm and some of its real-life applications.</li> </ul> <hr></nodes;> הֶסבֵּר:
בקטע הקוד שלמעלה, הגדרנו מחלקה ציבורית בתור DijkstraAlgorithm() . בתוך המחלקה הזו, הגדרנו שיטה ציבורית בתור dijkstraAlgorithm() כדי למצוא את המרחק הקצר ביותר מקודקוד המקור לקודקוד היעד. בתוך שיטה זו, הגדרנו משתנה לאחסון מספר הצמתים. לאחר מכן הגדרנו מערך בוליאני לאחסן את המידע לגבי הקודקודים שבהם ביקר ומערך שלמים לאחסון המרחקים שלהם. בתחילה, הכרזנו על הערכים בשני המערכים כ שֶׁקֶר ו ערך מקסימלי , בהתאמה. קבענו גם את המרחק של קודקוד המקור כאפס והשתמשנו ב- for-loop כדי לעדכן את המרחק בין קודקוד המקור לקודקודי היעד עם המרחק המינימלי. לאחר מכן עדכנו את המרחקים של הקודקודים הסמוכים של הקודקוד שנבחר על ידי ביצוע הרפיה והדפסנו את המרחקים הקצרים ביותר עבור כל קודקוד. לאחר מכן הגדרנו שיטה למצוא את המרחק המינימלי מקודקוד המקור לקודקוד היעד. לאחר מכן הגדרנו את הפונקציה הראשית שבה הכרזנו על קודקודי הגרף והצגנו את ה DijkstraAlgorithm() מעמד. לבסוף, קראנו ל- dijkstraAlgorithm() שיטה למצוא את המרחק הקצר ביותר בין קודקוד המקור לקודקודי היעד.
כתוצאה מכך, הנתיבים הקצרים ביותר הנדרשים עבור כל צומת מצומת המקור מודפסים עבור המשתמשים.
css טקסט קו תחתון
קוד לאלגוריתם של דיקסטרה ב-Python
להלן יישום האלגוריתם של דיקסטרה בשפת התכנות Python:
קובץ: DikstraAlgorithm.py
# Implementation of Dijkstra's Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print('Distance of', chr(ord('A') + i), 'from source node:', distance[1]) i = i + 1 </0>
תְפוּקָה
Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3
הֶסבֵּר:
בקטע הקוד שלמעלה, ייבאנו את sys מודול והכריז על הרשימות המורכבות מהערכים של הצמתים והקצוות. לאחר מכן הגדרנו פונקציה כ toBeVisited() כדי למצוא באיזה צומת יבקר הבא. לאחר מכן מצאנו את המספר הכולל של צמתים בגרף והגדרנו את המרחקים ההתחלתיים עבור כל צומת. לאחר מכן חישבנו את המרחק המינימלי מצומת המקור לצומת היעד, ביצענו הרפיה בצמתים שכנים ועדכנו את המרחקים ברשימה. לאחר מכן הדפסנו את המרחקים האלה מהרשימה עבור המשתמשים.
כתוצאה מכך, הנתיבים הקצרים ביותר הנדרשים עבור כל צומת מצומת המקור מודפסים עבור המשתמשים.
מורכבות זמן ומרחב של האלגוריתם של דיקסטרה
- מורכבות הזמן של האלגוריתם של דיקסטרה היא O(E log V) , כאשר E הוא מספר הקצוות ו-V הוא מספר הקודקודים.
- מורכבות החלל של האלגוריתם של דיקסטרה היא O(V), כאשר V הוא מספר הקודקודים.
היתרונות והחסרונות של האלגוריתם של דיקסטרה
הבה נדון בכמה יתרונות של האלגוריתם של דיקסטרה:
- יתרון עיקרי אחד בשימוש באלגוריתם של דיקסטרה הוא שיש לו מורכבות זמן ומרחב כמעט ליניארית.
- אנו יכולים להשתמש באלגוריתם זה כדי לחשב את הנתיב הקצר ביותר מקודקוד בודד לכל שאר הקודקודים וקודקוד מקור בודד לקודקוד יעד בודד על ידי עצירת האלגוריתם ברגע שנקבל את המרחק הקצר ביותר עבור קודקוד היעד.
- אלגוריתם זה עובד רק עבור גרפים משוקללים מכוונים, וכל הקצוות של גרף זה צריכים להיות לא שליליים.
למרות יתרונות מרובים, לאלגוריתם של דיקסטרה יש גם כמה חסרונות, כגון:
- האלגוריתם של דיקסטרה מבצע חקירה סמויה שמנצלת זמן רב במהלך התהליך.
- אלגוריתם זה אינו יכול להתמודד עם קצוות שליליים.
- מכיוון שהאלגוריתם הזה פונה לגרף האציקלי, הוא לא יכול לחשב את הנתיב הקצר ביותר במדויק.
- זה גם דורש תחזוקה כדי לשמור תיעוד של קודקודים שביקרו בהם.
כמה יישומים של האלגוריתם של דיקסטרה
לאלגוריתם של Dijkstra יש יישומים שונים בעולם האמיתי, שחלקם מופיעים להלן:
המסקנה
- במדריך לעיל, ראשית, הבנו את המושגים הבסיסיים של גרף יחד עם סוגיו ויישומיו.
- לאחר מכן למדנו על האלגוריתם של דיקסטרה וההיסטוריה שלו.
- הבנו גם את העבודה הבסיסית של האלגוריתם של דיקסטרה בעזרת דוגמה.
- לאחר מכן, למדנו כיצד לכתוב קוד עבור האלגוריתם של דיקסטרה בעזרת פסאודוקוד.
- צפינו ביישום שלו בשפות תכנות כמו C, C++, Java ו-Python עם פלטים והסברים מתאימים.
- הבנו גם את מורכבות הזמן והמרחב של האלגוריתם של דיקסטרה.
- לבסוף, דנו ביתרונות ובחסרונות של האלגוריתם של דיקסטרה וחלק מהיישומים האמיתיים שלו.