آنچه آنها در مصاحبه می پرسند: بررسی الگوریتم ها، بخش 2

این مقاله ادامه بررسی کوتاه من در مورد الگوریتم ها است. اینم لینک قسمت اول قبلاً، الگوریتم‌های مرتب‌سازی آرایه‌های مختلف و به اصطلاح الگوریتم حریص را بررسی کردیم . امروز در مورد نمودارها و الگوریتم های مربوط به آنها صحبت خواهیم کرد. گراف یکی از انعطاف پذیرترین و همه کاره ترین ساختارها در برنامه نویسی است. یک نمودار G معمولاً با استفاده از یک جفت مجموعه G = (V, R) مشخص می شود که در آن:

• V - مجموعه ای از رئوس.
• R مجموعه خطوطی است که جفت رئوس را به هم متصل می کند.

خطوط اتصال معمولی لبه نامیده می شوند : خطوط دارای فلش - کمان : به طور معمول، یک نمودار با استفاده از نموداری نشان داده می شود که در آن برخی از رئوس با یال ها (قوس) به هم متصل می شوند. گراف هایی که با کمان هایی که مستقیماً جهت را نشان می دهند به یکدیگر متصل می شوند جهت دار نامیده می شوند . اگر نمودارها توسط یال ها به هم متصل شوند، یعنی بدون نشان دادن جهت حرکت احتمالی، بدون جهت می شوند . این بدان معنی است که حرکت در امتداد آنها در هر دو جهت امکان پذیر است: هم از راس A به B، و هم از B به A. گراف متصل ، نموداری است که در آن حداقل یک مسیر از هر راس به هر راس دیگری منتهی می شود (مانند مثال). در بالا ). اگر اینطور نباشد، نمودار قطع می‌شود : همچنین، به یال‌ها (قوس‌ها) می‌توان وزن‌هایی اختصاص داد - اعدادی که فاصله فیزیکی بین دو راس (یا زمان نسبی انتقال بین دو راس) را نشان می‌دهند. چنین نمودارهایی وزن دار نامیده می شوند :

3. الگوریتم های جستجوی مسیر (عمق، عرض)

یکی از عملیات اساسی که بر روی نمودارها انجام می شود، تعیین تمام رئوس هایی است که از یک راس معین قابل دسترسی هستند. تصور کنید که در حال تلاش برای تعیین نحوه رسیدن از شهری به شهر دیگر با نقل و انتقالات احتمالی هستید. دسترسی مستقیم به برخی شهرها وجود دارد، در حالی که برخی دیگر نیاز به انحراف از طریق شهرهای دیگر دارند. موقعیت‌های بسیار دیگری وجود دارد که در آن‌ها ممکن است لازم باشد تمام رئوس‌هایی را که می‌توان مسیری به آن‌ها را از یک راس مشخص پیدا کرد، پیدا کرد. بنابراین، دو راه اصلی برای پیمایش نمودارها وجود دارد: پیمایش اول عمق و پیمایش عرض اول ، که ما آنها را بررسی خواهیم کرد. هر دو روش از تکرار در تمام رئوس متصل اطمینان حاصل می کنند. برای بررسی بیشتر الگوریتم‌های عمق اول و عرض اول ، نمودار زیر را در نظر بگیرید:

پیمایش اول عمق

این یکی از رایج ترین روش های پیمایش نمودار است. این استراتژی جستجوی عمقی شامل رفتن به عمق نمودار تا آنجا که ممکن است، و پس از رسیدن به بن بست، بازگشت به نزدیکترین راس است که دارای رئوس مجاور است که قبلاً بازدید نشده است. این الگوریتم اطلاعاتی را در پشته ذخیره می کند که در صورت رسیدن به بن بست کجا باید برگردد. قوانین برای اولین پیمایش عمق:

1. از یک راس مجاور که قبلاً بازدید نشده بود دیدن کنید، آن را علامت بزنید و روی پشته قرار دهید.
2. به این رأس بروید.
3. مرحله 1 را تکرار کنید.
4. اگر تکمیل مرحله 1 غیرممکن است، به راس قبلی برگردید و سعی کنید قانون 1 را تکرار کنید. اگر این غیرممکن است، به راس قبل از آن برگردید و همینطور ادامه دهید، تا زمانی که یک راس پیدا کنیم که بتوانیم پیمایش را از آن ادامه دهیم.
5. ادامه دهید تا همه رئوس روی پشته قرار گیرند.

بیایید نگاهی بیندازیم که کد این الگوریتم ممکن است در جاوا چگونه باشد:

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();
  }
}

خروجی کنسول: از آنجایی که ما یک ماتریس مجاورت داریم و در روش walk از یک حلقه تو در تو در یک حلقه استفاده می کنیم، پیچیدگی زمانی O(N²) خواهد بود .

خزیدن گسترده

این الگوریتم نیز مانند پیمایش عمق، یکی از ساده ترین و ابتدایی ترین روش ها برای پیمایش گراف است. ماهیت آن این است که ما یک راس جریان مشخصی داریم که از آن همه راس های مجاور و بدون پیمایش را در یک صف قرار می دهیم و عنصر بعدی (که ابتدا در صف ذخیره می شود) را انتخاب می کنیم تا آن را به جریان تبدیل کنیم... اگر این الگوریتم را به مراحل، می توانیم قوانین زیر را برجسته کنیم:

1. از رأس بعدی که قبلاً بازدید نشده است در مجاورت راس فعلی بازدید کنید، آن را از قبل علامت بزنید و به صف اضافه کنید.
2. اگر قانون شماره 1 قابل اجرا نیست، راس را از صف حذف کرده و آن را به راس فعلی تبدیل کنید.
3. اگر قوانین #1 و #2 غیرممکن باشند، پیمایش کامل شده و تمام رئوس پیمایش شده اند (اگر گراف ما متصل باشد).

کلاس گراف تقریباً با کلاس مشابه از الگوریتم جستجوی عمقی یکسان است، به جز روشی که الگوریتم را پردازش می کند و پشته داخلی را با یک صف جایگزین می کند:

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 با کلاس الگوریتم جستجوی depth-first یکسان است . بیایید این الگوریتم را عملی کنیم:

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. الگوریتم دایکسترا

همانطور که قبلا ذکر شد، نمودارها می توانند جهت دار یا بدون جهت باشند . و همانطور که به یاد دارید، آنها هنوز هم می توانند وزن شوند . نمودارهای وزن دار و جهت دار اغلب در زندگی واقعی یافت می شوند: به عنوان مثال، نقشه شهرها، که در آن شهرها راس هستند، مسیرهای بین آنها جاده ها هستند، جاده ها می توانند ترافیک یک طرفه داشته باشند - جهت نمودار. فرض کنید شما مشغول حمل و نقل بار هستید و باید کوتاه ترین مسیر را بین دو شهر دور ایجاد کنید. چطور این کار رو می کنی؟ یکی از رایج ترین مشکلات مربوط به نمودارهای وزنی، مشکل انتخاب کوتاه ترین مسیر بین دو راس است. برای حل این مشکل از الگوریتم Dijkstra استفاده می کنیم . می‌خواهم فوراً متذکر شوم که با اجرای الگوریتم Dijkstra، کوتاه‌ترین مسیرها را برای همه رئوس از یک ابتدایی مشخص پیدا خواهیم کرد. این الگوریتم چه مراحلی دارد؟ من سعی می کنم به این سوال پاسخ دهم. مراحل الگوریتم دایکسترا:

• مرحله 1 : جستجو برای گره، که انتقال به آن کمترین هزینه را خواهد داشت. شما در همان ابتدا ایستاده اید و به این فکر می کنید که به کجا بروید: به گره A یا به گره B. چقدر طول می کشد تا به هر یک از این گره ها برسیم؟
• مرحله 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. ما کوتاه ترین مسیر به همسایه خود را پیدا می کنیم - G.

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

   در واقع، در اینجا مسیر A تا G را پیدا کرده ایم.

   اما برای اطمینان از اینکه کوتاه ترین است، باید مراحل خود را برای راس E نیز اجرا کنیم .

9. از آنجایی که راس G دارای رئوس مجاوری نیست که یک مسیر هدایت شده به آن منتهی شود، فقط راس E باقی مانده است : آن را انتخاب می کنیم.
10. ما کوتاه ترین مسیر به همسایه را پیدا می کنیم - G.

    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²) نیست زیرا ما حلقه‌هایی درون یک حلقه داریم. خب، این همه برای من امروز است، از توجه شما متشکرم!