ڇا اهي هڪ انٽرويو ۾ پڇن ٿا: الگورتھم جو جائزو، حصو 2

هي آرٽيڪل الگورٿم تي منهنجي مختصر جائزي جو تسلسل آهي. هتي پهرين حصي جي لنڪ آهي . اڳي، اسان مختلف صفن کي ترتيب ڏيڻ واري الگورتھم ۽ نام نهاد لالچي الگورتھم کي ڏٺو . اڄ اسان انهن سان لاڳاپيل گرافس ۽ الگورتھم بابت ڳالهائينداسين. هڪ گراف پروگرامنگ ۾ سڀ کان وڌيڪ لچڪدار ۽ آفاقي جوڙجڪ مان هڪ آهي. هڪ گراف G عام طور تي مقرر ڪيو ويندو آهي سيٽن جي هڪ جوڙي استعمال ڪندي G = (V، R) ، جتي:

• V عمودي جو سيٽ آهي؛
• R قطارن جو سيٽ آھي جيڪو ڳنڍيندڙ جوڙن جي چوٽي کي.

عام ڳنڍيندڙ لائينن کي ڪنڊن (Edges) چئبو آهي : تير سان ليڪون - arcs : عام طور تي، هڪ گراف کي ڏيکاريو ويندو آهي هڪ ڊاگرام استعمال ڪندي جنهن ۾ ڪجهه چوڪيون ڪنارن سان ڳنڍيل آهن (arcs). هڪ ٻئي سان ڳنڍيل گرافس جيڪي سڌو سنئون طرف اشارو ڪن ٿا آرڪس کي هدايت سڏيو ويندو آهي . جيڪڏهن گراف ڪنارن سان ڳنڍيل آهن، اهو آهي، ممڪن حرڪت جي هدايت جي بغير، اهي اڻ سڌي ٿي ويندا آهن . ان جو مطلب اهو آهي ته انهن سان گڏ حرڪت ٻنهي طرفن ۾ ممڪن آهي: ٻنهي طرفن کان A کان B تائين، ۽ B کان A تائين. A ڳنڍيل گراف هڪ گراف آهي جنهن ۾ گهٽ ۾ گهٽ هڪ رستو هر ويرٽيڪس کان ڪنهن ٻئي عمدي ڏانهن وڃي ٿو (جيئن مثال ۾. مٿي). جيڪڏهن اهو معاملو نه آهي، گراف ڌار ٿي ويندو آهي : پڻ، ڪنارن (آرڪس) کي وزن مقرر ڪري سگهجي ٿو - انگن اکرن جي وچ ۾ جسماني فاصلي جي نمائندگي ڪن ٿا (يا ٻن چوڪن جي وچ ۾ منتقلي جو لاڳاپو وقت). اهڙن گراف کي وزني چئبو آهي :

3. رستو ڳولها الگورتھم (کوٽائي، ويڪر)

بنيادي ڪمن مان هڪ آهي جيڪي گرافس تي ڪيا ويا آهن انهن سڀني عمودين کي طئي ڪرڻ آهي جيڪي ڏنل عمودي کان پهچي سگهجن ٿيون. تصور ڪريو ته توهان اهو طئي ڪرڻ جي ڪوشش ڪري رهيا آهيو ته ممڪن منتقلي سان هڪ شهر کان ٻئي تائين ڪيئن حاصل ڪجي. ڪجهه شهرن کي سڌو سنئون پهچي سگهجي ٿو، جڏهن ته ٻين کي ٻين شهرن ذريعي رستي جي ضرورت آهي. اهڙيون ٻيون به ڪيتريون ئي حالتون آهن جن ۾ اهو ضروري ٿي سگهي ٿو ته انهن سڀني چوڪن کي ڳولجي، جن ڏانهن هڪ ڏنل ويڪر مان رستو ڳولي سگهجي ٿو. تنهن ڪري، گرافس کي ڇڪڻ جا ٻه مکيه طريقا آهن: ڊيپٿ فرسٽ ٽرورسل ۽ بيڊٿ فرسٽ ٽرورسل ، جنهن تي اسين غور ڪنداسين. ٻنهي طريقن کي يقيني بڻائي سگهندي ته سڀني جڙيل عمودي تي ٻيهر ورجائي ٿو. Depth-first ۽ breadth-first algorithms تي وڌيڪ غور ڪرڻ لاءِ ، ھيٺ ڏنل گراف وٺو:

Depth First Traversal

هي سڀ کان عام گراف ٽرورسل طريقن مان هڪ آهي. هيءَ کوٽائي -پهرين ڳولا واري حڪمت عملي تي مشتمل آهي ”گڏيل“ ۾ جيترو ٿي سگهي گراف ۾ وڃڻ، ۽ جڏهن ختم ٿيڻ تي پهچجي ته، ويجھي ويجھي چوٽيءَ ڏانهن موٽڻ، جنهن جي ڀرپاسي واريون چوٽيون آهن جن کي اڳي نه ڏٺو ويو آهي. هي الورورٿم اسٽيڪ تي معلومات محفوظ ڪري ٿو ته ڪٿي واپس وڃڻو آهي جڏهن هڪ تعطل پهچي وڃي. قاعدن جي پهرين کوٽائي لاء:

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

ڪنسول آئوٽ: جيئن ته اسان وٽ هڪ ويجهڙائي وارو ميٽرڪس آهي ۽ هلڻ جي طريقي ۾ اسان لوپ اندر اندر اندر ٿيل لوپ استعمال ڪندا آهيون، وقت جي پيچيدگي 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 ڪلاس ڊيپٿ فرسٽ سرچ الگورٿم کان ڪلاس سان هڪجهڙائي رکي ٿو . اچو ته هن الگورتھم کي عمل ۾ رکون:

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 جي الگورتھم . مان فوري طور تي نوٽ ڪرڻ چاهيان ٿو ته Dijkstra جي الگورٿم تي عمل ڪرڻ سان اسان هڪ ڏنل ابتدائي هڪ کان سڀني چوڪن ڏانهن ننڍو رستا ڳولي سگهنداسين. هن الورورٿم جا ڪهڙا مرحلا آهن؟ مان هن سوال جو جواب ڏيڻ جي ڪوشش ڪندس. Dijkstra جي الگورتھم قدم:

• اسٽيج 1 : نوڊ جي ڳولا ڪريو، جنهن جي منتقلي گهٽ ۾ گهٽ قيمت هوندي. توهان بلڪل شروعات ۾ بيٺا آهيو ۽ حيران ٿي رهيا آهيو ته ڪيڏانهن وڃو: نوڊ اي يا نوڊ بي ڏانهن. انهن مان هر هڪ کي حاصل ڪرڻ لاء ڪيترو وقت وٺندو؟
• اسٽيج 2 : حساب ڪرڻ ڪيترو وقت وٺندو آهي B جي سڀني پاڙيسرين تائين پهچڻ ۾ جيڪي اڃا تائين الورورٿم کان متاثر نه ٿيا آهن جڏهن B کان هڪ ڪنڊ سان هلڻ دوران. جيڪڏهن اهو نئون وقت پراڻي وقت کان گهٽ نڪرندو آهي، ته ڪناري B ذريعي رستو هن ويڪر لاءِ نئون ننڍو رستو بڻجي ويندو.
• اسٽيج 3 : عمودي بي کي نشان لڳايو جيئن گذري ويو.
• قدم 4 : قدم 1 ڏانھن وڃو.

اسان انهن مرحلن جي چڪر کي ورجائينداسين جيستائين سڀئي چوٽيون گذري وڃن. اچو ته ھيٺ ڏنل وزن واري ھدايت واري گراف تي غور ڪريون: تنھنڪري، مٿين الگورتھم کي استعمال ڪندي، اسين A کان G تائين ننڍو رستو طئي ڪنداسين:

1. vertex A لاءِ ٽي ممڪن رستا آھن: B ڏانھن 3 جي وزن سان، C ڏانھن 5 جي وزن سان ۽ D ڏانھن 7 جي وزن سان. الگورتھم جي پھرين نقطي جي مطابق، اسان سڀ کان گھٽ منتقلي سان نوڊ کي چونڊيو آھي. قيمت - يعني بي .
2. جيئن ته B لاءِ صرف اڻ چٽو پاڙيسري ويڪرو vertex E آهي ، اسان چيڪ ڪريون ٿا ته رستو ڪهڙو هوندو جڏهن هن عمدي مان لنگهي. 3 ( AB ) + 6 ( BE ) = 9.

   ان ڪري، اسان نوٽ ڪيو ته موجوده ننڍو رستو AE = 9 تائين.

3. جيئن ته اسان جو ڪم vertex B سان اڳ ۾ ئي مڪمل ٿي چڪو آهي، اسان اڳتي وڌون ٿا ته ان کان اڳ واري ڪنڊ جي گهٽ ۾ گهٽ وزن سان ايندڙ ويڪر کي چونڊڻ لاءِ.

   عمودي A ۽ B مان اهي عمودي ڊي (7)، سي (5)، اي (6) ٿي سگهن ٿا.

   C وٽ ننڍي کنڊ جو وزن آهي ، تنهنڪري اسان اڳتي وڌون ٿا هن ويڪر ڏانهن.

4. اڳيون، جيئن اڳي، اسان ڳوليون ٿا ننڍو رستو پاڙيسري عمودي ڏانهن جڏهن لنگهي سي:
   • AD = 5( AC ) + 3 ( CD ) = 8، پر جيئن ته پوئين ننڍو رستو AC = 7، اھو آھي، ھن ھڪڙي کان گھٽ C ذريعي ، اسان ننڍو رستو ڇڏي ڏيون ٿا AD = 7 اڻ تبديل ٿيل.
   • CE = 5 ( AC ) + 4 ( CE ) = 9، هي نئون ننڍو رستو اڳئين رستي جي برابر آهي، تنهن ڪري اسان ان کي به بدلائي ڇڏيون ٿا.
5. ويجھي موجود ڪنارن مان، E ۽ D ، اسان ننڍي کنڊ جي وزن سان، يعني ڊي (3) کي چونڊيندا آھيون.
6. اسان ان جي پاڙيسري ڏانهن ننڍو رستو ڳوليندا آهيون - ايف.

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

7. ويجھي موجود ڪنارن E ۽ F مان ، اسان ان ويڙھيءَ کي چونڊون ٿا جنھن جي ڪنارن جي گھٽ ۾ گھٽ وزن آھي، يعني F (3).
8. اسان ان جي پاڙيسري ڏانهن ننڍو رستو ڳوليندا آهيون - جي.

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

   دراصل، هتي اسان کي A کان G تائين رستو مليو آهي.

   پر پڪ ڪرڻ لاءِ ته اهو ننڍو آهي، اسان کي اسان جي قدمن کي هلائڻ گهرجي vertex E لاءِ پڻ .

9. جيئن ته vertex G وٽ پاڙيسري عمودي نه آھن جن ڏانھن ھدايت ڪيل رستو ھلندو، اسان وٽ صرف vertex E ڇڏي ويو آھي : اسان ان کي چونڊيو.
10. اسان پاڙيسري ڏانهن ننڍو رستو ڳوليندا آهيون - جي.

    AG = 3 ( AB ) + 6 ( BE ) + 6 ( EG ) = 15، ھي رستو اڳئين مختصر ترين AG (14) کان ڊگھو آھي، تنھنڪري اسين ھن رستي کي اڻڄاڻائي ڇڏيون ٿا.

    جيئن ته G کان ڪي به چوڪيدار نه آهن ، ان لاءِ ڏنل عمدي لاءِ مرحلن کي هلائڻ جو ڪو به مطلب ناهي. تنهن ڪري، الورورٿم جو ڪم مڪمل سمجهي سگهجي ٿو.

جيئن مون اڳ ۾ چيو آهي ته، AG لاءِ مختصر ترين رستو ڳولڻ کان علاوه ، اسان کي vertex 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²) کان وڌيڪ ڪجهه به ناهي ڇو ته اسان وٽ لوپ هڪ لوپ اندر داخل ٿيل آهن. خير، اهو سڀ ڪجهه اڄ مون لاءِ آهي، توهان جي توجه لاءِ مهرباني!