מה הם שואלים בראיון: סקירת אלגוריתמים, חלק 2

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

• V הוא קבוצת הקודקודים;
• R הוא קבוצת הקווים המחברים בין זוגות קודקודים.

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

3. אלגוריתמים לחיפוש נתיבים (עומק, רוחב)

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

מעבר עומק ראשון

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

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

בואו נסתכל איך הקוד של האלגוריתם הזה עשוי להיראות ב-Java:

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexArray[]; //массив вершин
  private int adjMat[][]; // матрица смежности
  private int nVerts; // текущее количество вершин
  private Stack<integer> stack;

  public Graph() { // инициализация внутрених полей
     vertexArray = new Vertex[MAX_VERTS];
     adjMat = new int[MAX_VERTS][MAX_VERTS];
     nVerts = 0;
     for (int j = 0; j < MAX_VERTS; j++) {
        for (int k = 0; k < MAX_VERTS; k++) {
           adjMat[j][k] = 0;
        }
     }
     stack = new Stack<>();
  }

  public void addVertex(char lab) {
     vertexArray[nVerts++] = new Vertex(lab);
  }

  public void addEdge(int start, int end) {
     adjMat[start][end] = 1;
     adjMat[end][start] = 1;
  }

  public void displayVertex(int v) {
     System.out.println(vertexArray[v].getLabel());
  }

  public void dfs() { // обход в глубину
     vertexArray[0].setWasVisited(true); // берётся первая вершина
     displayVertex(0);
     stack.push(0);

     while (!stack.empty()) {
        int v = getAdjUnvisitedVertex(stack.peek()); // вынуть индекс смежной веришины, еckи есть 1, нету -1
        if (v == -1) { // если непройденных смежных вершин нету
           stack.pop(); // элемент извлекается из стека
        }
        else {
           vertexArray[v].setWasVisited(true);
           displayVertex(v);
           stack.push(v); // элемент попадает на вершину стека
        }
     }

     for (int j = 0; j < nVerts; j++) {  // сброс флагов
        vertexArray[j].wasVisited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexArray[j].wasVisited == false) {
           return j; //возвращает первую найденную вершину
        }
     }
     return -1;
  }
}
</integer>

החלק העליון נראה כך:

public class Vertex {
  private char label;  // метка А например
  public boolean wasVisited;

  public Vertex(final char label) {
     this.label = label;
     wasVisited = false;
  }

  public char getLabel() {
     return this.label;
  }

  public boolean isWasVisited() {
     return this.wasVisited;
  }

  public void setWasVisited(final boolean wasVisited) {
     this.wasVisited = wasVisited;
  }
}

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

public class Solution {
  public static void main(String[] args) {
     Graph graph = new Graph();
     graph.addVertex('A'); //0
     graph.addVertex('B'); //1
     graph.addVertex('C'); //2
     graph.addVertex('D'); //3
     graph.addVertex('E'); //4
     graph.addVertex('F'); //5
     graph.addVertex('G'); //6

     graph.addEdge(0,1);
     graph.addEdge(0,2);
     graph.addEdge(0,3);
     graph.addEdge(1,4);
     graph.addEdge(3,5);
     graph.addEdge(5,6);

     System.out.println("Visits: ");
     graph.dfs();
  }
}

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

ללכת לרוחב

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

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

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

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexList[]; //массив вершин
  private int adjMat[][]; // матрица смежности
  private int nVerts; // текущее количество вершин
  private Queue<integer> queue;

  public Graph() {
     vertexList = new Vertex[MAX_VERTS];
     adjMat = new int[MAX_VERTS][MAX_VERTS];
     nVerts = 0;
     for (int j = 0; j < MAX_VERTS; j++) {
        for (int k = 0; k < MAX_VERTS; k++) {  // заполнение матрицы смежности нулями
           adjMat[j][k] = 0;
        }
     }
     queue = new PriorityQueue<>();
  }

  public void addVertex(char lab) {
     vertexList[nVerts++] = new Vertex(lab);
  }

  public void addEdge(int start, int end) {
     adjMat[start][end] = 1;
     adjMat[end][start] = 1;
  }

  public void displayVertex(int v) {
     System.out.println(vertexList[v].getLabel());
  }

  public void bfc() { // обход в глубину
     vertexList[0].setWasVisited(true);
     displayVertex(0);
     queue.add(0);
     int v2;

     while (!queue.isEmpty()) {
        int v = queue.remove();

        while((v2 = getAdjUnvisitedVertex(v))!=-1) {// цикл будет работать, пока все смежные вершины не будут найденны, и не будут добавлены в очередь
           vertexList[v2].wasVisited =true;
           displayVertex(v2);
           queue.add(v2);
        }
     }

     for (int j = 0; j < nVerts; j++) {  // сброс флагов
        vertexList[j].wasVisited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false) {
           return j; //возвращает первую найденную вершину
        }
     }
     return -1;
  }
}
</integer>

מחלקת Vertex זהה למחלקה מאלגוריתם החיפוש העומק-ראשון . בואו נפעיל את האלגוריתם הזה:

public class Solution {
  public static void main(String[] args) {
     Graph graph = new Graph();
     graph.addVertex('A'); //0
     graph.addVertex('B'); //1
     graph.addVertex('C'); //2
     graph.addVertex('D'); //3
     graph.addVertex('E'); //4
     graph.addVertex('F'); //5
     graph.addVertex('G'); //6

     graph.addEdge(0,1);
     graph.addEdge(0,2);
     graph.addEdge(0,3);
     graph.addEdge(1,4);
     graph.addEdge(3,5);
     graph.addEdge(5,6);

     System.out.println("Visits: ");
     graph.bfc();
  }
}

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

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

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

• שלב 1 : חפש את הצומת, שהמעבר אליו יהיה העלות הנמוכה ביותר. אתה עומד ממש בהתחלה ותוהה לאן ללכת: לצומת א' או לצומת ב' . כמה זמן ייקח להגיע לכל אחד מהצמתים הללו?
• שלב 2 : חישוב כמה זמן לוקח להגיע לכל השכנים של B שעדיין לא הושפעו מהאלגוריתם בעת תנועה לאורך קצה מ- B. אם הזמן החדש הזה יתברר כפחות מהישן, השביל דרך קצה B יהפוך לנתיב הקצר החדש ביותר עבור קודקוד זה.
• שלב 3 : סמן את קודקוד B כעבר.
• שלב 4 : עבור לשלב 1.

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

1. לקודקוד A ישנם שלושה נתיבים אפשריים: ל- B במשקל 3, ל- C במשקל 5 ול- D במשקל 7. לפי הנקודה הראשונה של האלגוריתם, נבחר את הצומת עם המעבר הנמוך ביותר עלות - כלומר ל- B.
2. מכיוון שהקודקוד השכן היחיד שאינו עובר ל- B הוא קודקוד E , אנו בודקים מה יהיה הנתיב במעבר דרך קודקוד זה. 3( AB ) + 6( BE ) = 9.

   לפיכך, נציין שהנתיב הקצר ביותר הנוכחי ל-AE = 9.

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

   מקודקודים A ו- B אלה יכולים להיות קודקודים D (7), C (5), E (6).

   ל- C יש את משקל הקצה הקטן ביותר , אז נמשיך לקודקוד הזה.

4. לאחר מכן, כמו קודם, אנו מגלים את הדרך הקצרה ביותר לקודקודים שכנים כאשר אנו עוברים דרך C:
   • AD = 5( AC ) + 3( CD ) = 8, אך מכיוון שהנתיב הקצר ביותר הקודם AC = 7, כלומר פחות מזה דרך C , נשאיר את הנתיב הקצר ביותר AD = 7 ללא שינוי.
   • CE = 5( AC ) + 4( CE ) = 9, הנתיב הקצר ביותר החדש הזה שווה לקודם ולכן נשאיר אותו ללא שינוי.
5. מהקודקודים הזמינים הקרובים ביותר, E ו- D , אנו בוחרים את הקודקוד עם משקל הקצה הקטן ביותר, כלומר D (3).
6. אנו מגלים את הדרך הקצרה ביותר לשכנתה - F.

   AF = 7( AD ) + 3( DF ) = 10

7. מהקודקודים הזמינים הקרובים ביותר E ו- F , אנו בוחרים את הקודקוד עם המשקל הנמוך ביותר של הקצה אליו, כלומר F (3).
8. אנו מגלים את הדרך הקצרה ביותר לשכנתה - ג'.

   AG = 7( AD ) + 3( DF ) + 4( FG ) = 14

   למעשה, כאן מצאנו את הנתיב מ- A ל- G.

   אבל כדי לוודא שהוא הקצר ביותר, עלינו להפעיל את הצעדים שלנו גם עבור קודקוד E.

9. מכיוון שלקודקוד G אין קודקודים סמוכים אליהם יוביל נתיב מכוון, נותר לנו רק קודקוד E : אנו בוחרים בו.
10. אנחנו מגלים את הדרך הקצרה ביותר אל השכן - ג' .

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, נתיב זה ארוך מה-AG(14) הקצר ביותר, לכן נשאיר את הנתיב הזה ללא שינוי.

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

כפי שאמרתי קודם, בנוסף למציאת הנתיב הקצר ביותר עבור AG , קיבלנו את הנתיבים הקצרים ביותר לכל הקודקודים מקודקוד A (AB, AC, AD, AE, AF) . ובכן, הגיע הזמן להסתכל כיצד ניתן ליישם זאת בג'אווה. ראשית, בואו נסתכל על מחלקת הקודקוד:

public class Vertex {
   private char label;
   private boolean isInTree;

   public Vertex(char label) {
       this.label = label;
       this.isInTree = false;
   }

   public char getLabel() {
       return label;
   }

   public void setLabel(char label) {
       this.label = label;
   }

   public boolean isInTree() {
       return isInTree;
   }

   public void setInTree(boolean inTree) {
       isInTree = inTree;
   }
}

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

public class Path { // an object данного класса содержащий расстояние и предыдущие и пройденные вершины
   private int distance; // текущая дистанция от начальной вершины
   private List<integer> parentVertices; // текущий родитель вершины

   public Path(int distance) {
       this.distance = distance;
       this.parentVertices = new ArrayList<>();
   }

   public int getDistance() {
       return distance;
   }

   public void setDistance(int distance) {
       this.distance = distance;
   }

   public List<integer> getParentVertices() {
       return parentVertices;
   }

   public void setParentVertices(List<integer> parentVertices) {
       this.parentVertices = parentVertices;
   }
}
</integer></integer></integer>

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

public class Graph {
   private final int MAX_VERTS = 10;// максимальное количество вершин
   private final int INFINITY = 100000000; // это число у нас будет служить в качестве "бесконечности"
   private Vertex vertexList[]; // список вершин
   private int relationMatrix[][]; // матрица связей вершин
   private int countOfVertices; // текущее количество вершин
   private int countOfVertexInTree; // количество рассмотренных вершин в дереве
   private List<path> shortestPaths; // список данных кратчайших путей
   private int currentVertex; // текущая вершина
   private int startToCurrent; //расстояние до currentVertex

   public Graph() {
       vertexList = new Vertex[MAX_VERTS]; // матрица смежности
       relationMatrix = new int[MAX_VERTS][MAX_VERTS];
       countOfVertices = 0;
       countOfVertexInTree = 0;
       for (int i = 0; i < MAX_VERTS; i++) {// матрица смежности заполняется
           for (int k = 0; k < MAX_VERTS; k++) { // бесконечными расстояниями
               relationMatrix[i][k] = INFINITY; // задания значений по умолчанию
               shortestPaths = new ArrayList<>();// задается пустым
           }
       }
   }

   public void addVertex(char lab) {// задание новых вершин
       vertexList[countOfVertices++] = new Vertex(lab);
   }

   public void addEdge(int start, int end, int weight) {
       relationMatrix[start][end] = weight; // задание ребер между вершинами, с весом между ними
   }

   public void path() { // выбор кратчайшего пути
       //  задание данных для стартовой вершины
       int startTree = 0; // стартуем с вершины 0
       vertexList[startTree].setInTree(true); // включение в состав дерева первого element
       countOfVertexInTree = 1;

       // заполнение коротких путей для вершин смежных с стартовой
       for (int i = 0; i < countOfVertices; i++) {
           int tempDist = relationMatrix[startTree][i];
           Path path = new Path(tempDist);
           path.getParentVertices().add(0);// первым родительским элементом, будет всегда стартовая вершина
           shortestPaths.add(path);
       }
       // пока все вершины не окажутся в дереве
       while (countOfVertexInTree < countOfVertices) { // выполняем, пока количество вершин в дереве не сравняется с общим количеством вершин
           int indexMin = getMin();//получаем индекс вершины с наименшей дистанцией, из вершин еще не входящих в дерево
           int minDist = shortestPaths.get(indexMin).getDistance();// минимальная дистанция вершины, из тек которые ещё не в дереве

           if (minDist == INFINITY) {
               System.out.println("В графе пристувствуют недостижимые вершины");
               break;// в случае если остались непройденными только недостижимые вершины, мы выходим из цикла
           } else {
               currentVertex = indexMin; // переводим указатель currentVert к текущей вершине
               startToCurrent = shortestPaths.get(indexMin).getDistance();// задаем дистанцию к текущей вершине
           }

           vertexList[currentVertex].setInTree(true);  //включение текущей вершины в дерево
           countOfVertexInTree++; // увеличиваем счетчик вершин в дереве
           updateShortestPaths(); // обновление списка кратчайших путей
       }

       displayPaths(); // выводим в консоль результаты
   }

   public void clean() { // очиска дерева
       countOfVertexInTree = 0;
       for (int i = 0; i < countOfVertices; i++) {
           vertexList[i].setInTree(false);
       }
   }

   private int getMin() {
       int minDist = INFINITY; // за точку старта взята "бесконечная" длина
       int indexMin = 0;
       for (int i = 1; i < countOfVertices; i++) {// для каждой вершины
           if (!vertexList[i].isInTree() && shortestPaths.get(i).getDistance() < minDist) { // если вершина ещё не ве дереве и её растояние меньше старого минимума
               minDist = shortestPaths.get(i).getDistance(); // задаётся новый минимум
               indexMin = i; // обновление индекса вершины содержащую минимаьную дистанцию
           }
       }
       return indexMin; //возвращает индекс вершины с наименшей дистанцией, из вершин еще не входящих в дерево
   }

   private void updateShortestPaths() {
       int vertexIndex = 1; // стартовая вершина пропускается
       while (vertexIndex < countOfVertices) { // перебор столбцов

           if (vertexList[vertexIndex].isInTree()) { // если вершина column уже включена в дерево, она пропускается
               vertexIndex++;
               continue;
           }
           // вычисление расстояния для одного element sPath
           // получение ребра от currentVert к column
           int currentToFringe = relationMatrix[currentVertex][vertexIndex];
           // суммирование всех расстояний
           int startToFringe = startToCurrent + currentToFringe;
           // определение расстояния текущего element vertexIndex
           int shortPathDistance = shortestPaths.get(vertexIndex).getDistance();

           // сравнение расстояния через currentVertex с текущим расстоянием в вершине с индексом vertexIndex
           if (startToFringe < shortPathDistance) {// если меньше, то у вершины под индексом vertexIndex будет задан новый кратчайший путь
               List<integer> newParents = new ArrayList<>(shortestPaths.get(currentVertex).getParentVertices());//создаём копию списка родителей вершины currentVert
               newParents.add(currentVertex);// задаём в него и currentVertex How предыдущий
               shortestPaths.get(vertexIndex).setParentVertices(newParents); // соохраняем новый маршут
               shortestPaths.get(vertexIndex).setDistance(startToFringe); // соохраняем новую дистанцию
           }
           vertexIndex++;
       }
   }

   private void displayPaths() { // метод для вывода кратчайших путей на экран
       for (int i = 0; i < countOfVertices; i++) {
           System.out.print(vertexList[i].getLabel() + " = ");
           if (shortestPaths.get(i).getDistance() == INFINITY) {
               System.out.println("0");
           } else {
               String result = shortestPaths.get(i).getDistance() + " (";
               List<integer> parents = shortestPaths.get(i).getParentVertices();
               for (int j = 0; j < parents.size(); j++) {
                   result += vertexList[parents.get(j)].getLabel() + " -> ";
               }
               System.out.println(result + vertexList[i].getLabel() + ")");
           }
       }
   }
}
</integer></integer></path>

למעשה, זה כל הקסם =) ובכן, עכשיו, בואו נסתכל על האלגוריתם הזה בפעולה:

public class Solution {

   public static void main(String[] args) {
       Graph graph = new Graph();
       graph.addVertex('A');
       graph.addVertex('B');
       graph.addVertex('C');
       graph.addVertex('D');
       graph.addVertex('E');
       graph.addVertex('F');
       graph.addVertex('G');

       graph.addEdge(0, 1, 3);
       graph.addEdge(0, 2, 5);
       graph.addEdge(0, 3, 7);
       graph.addEdge(1, 4, 6);
       graph.addEdge(2, 4, 4);
       graph.addEdge(2, 3, 3);
       graph.addEdge(3, 5, 3);
       graph.addEdge(4, 6, 6);
       graph.addEdge(5, 6, 4);

       System.out.println("Элементы имеют кратчайшие пути из точки A: ");
       graph.path();
       graph.clean();
   }
}

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