وہ انٹرویو میں کیا پوچھتے ہیں: الگورتھم کا جائزہ، حصہ 2

یہ مضمون الگورتھم پر میرے مختصر جائزے کا تسلسل ہے۔ پہلے حصے کا لنک یہ ہے ۔ پہلے، ہم نے مختلف صفوں کو ترتیب دینے والے الگورتھم اور نام نہاد لالچی الگورتھم کو دیکھا ۔ آج ہم ان سے متعلق گراف اور الگورتھم کے بارے میں بات کریں گے۔ گراف پروگرامنگ میں سب سے زیادہ لچکدار اور عالمگیر ڈھانچے میں سے ایک ہے۔ گراف G کو عام طور پر سیٹوں کے جوڑے کا استعمال کرتے ہوئے مخصوص کیا جاتا ہے G = (V, R) ، جہاں:

• V چوٹیوں کا مجموعہ ہے۔
• R خطوط کے جوڑوں کو جوڑنے والی لائنوں کا مجموعہ ہے۔

عام جڑنے والی لائنوں کو کنارے کہا جاتا ہے : تیروں والی لکیریں - آرکس : عام طور پر، ایک خاکہ کا استعمال کرتے ہوئے ایک گراف کو دکھایا جاتا ہے جس میں کچھ عمودی کناروں (آرکس) کے ذریعے جڑے ہوتے ہیں۔ آرکس کے ذریعے ایک دوسرے سے جڑے گراف براہ راست سمت کی نشاندہی کرتے ہیں انہیں ڈائریکٹڈ کہا جاتا ہے ۔ اگر گراف کناروں سے جڑے ہوئے ہیں، یعنی ممکنہ حرکت کی سمت کی نشاندہی کیے بغیر، وہ غیر مستقیم ہو جاتے ہیں ۔ اس کا مطلب یہ ہے کہ ان کے ساتھ حرکت دونوں سمتوں میں ممکن ہے: دونوں سمتوں میں A سے B تک، اور B سے A تک۔ ایک منسلک گراف ایک ایسا گراف ہے جس میں کم از کم ایک راستہ ہر ایک چوٹی سے کسی دوسرے سرے کی طرف جاتا ہے (جیسا کہ مثال میں اوپر)۔ اگر ایسا نہیں ہے تو، گراف منقطع ہو جاتا ہے : اس کے علاوہ، کناروں (آرکس) کو وزن بھی تفویض کیا جا سکتا ہے - اعداد جو دو چوٹیوں کے درمیان جسمانی فاصلے کی نمائندگی کرتے ہیں (یا دو چوٹیوں کے درمیان منتقلی کا رشتہ دار وقت)۔ ایسے گراف کو وزنی کہا جاتا ہے :

3. پاتھ سرچ الگورتھم (گہرائی، چوڑائی)

گرافس پر کیے جانے والے بنیادی آپریشنز میں سے ایک ان تمام چوٹیوں کا تعین کرنا ہے جو کسی دیے ہوئے چوٹی سے قابل رسائی ہیں۔ تصور کریں کہ آپ یہ طے کرنے کی کوشش کر رہے ہیں کہ ممکنہ منتقلی کے ساتھ ایک شہر سے دوسرے شہر کیسے جانا ہے۔ کچھ شہروں تک براہ راست پہنچا جا سکتا ہے، جبکہ دوسروں کو دوسرے شہروں سے گزرنے کی ضرورت ہوتی ہے۔ ایسی بہت سی دوسری حالتیں ہیں جن میں کسی دیے ہوئے چوٹی سے ان تمام اعضاء کو تلاش کرنا ضروری ہو سکتا ہے جہاں تک راستہ تلاش کیا جا سکتا ہے۔ لہذا، گراف کو عبور کرنے کے دو اہم طریقے ہیں: ڈیپتھ فرسٹ ٹراورسل اور بریڈتھ فرسٹ ٹراورسل ، جس پر ہم غور کریں گے۔ دونوں طریقے اس بات کو یقینی بنائیں گے کہ تمام منسلک چوٹیوں پر تکرار ہوتی ہے۔ depth-first اور wreadth-first الگورتھم پر مزید غور کرنے کے لیے ، درج ذیل گراف کو دیکھیں:

ڈیپتھ فرسٹ ٹراورسل

یہ گراف ٹراورسل کے سب سے عام طریقوں میں سے ایک ہے۔ اس گہرائی کی پہلی تلاش کی حکمت عملی گراف میں جہاں تک ممکن ہو "گہرائی" میں جانے پر مشتمل ہوتی ہے ، اور جب آخری سرے پر پہنچ جاتی ہے، تو قریب ترین چوٹی پر واپس جانا جس کے ملحقہ عمودی ہوتے ہیں جو پہلے نہیں دیکھے گئے تھے۔ یہ الگورتھم اسٹیک پر معلومات ذخیرہ کرتا ہے کہ جب تعطل تک پہنچ جائے تو کہاں واپس جانا ہے۔ پہلے گہرائی سے گزرنے کے اصول:

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>

ورٹیکس کلاس ڈیپتھ فرسٹ سرچ الگورتھم کی کلاس سے مماثل ہے ۔ آئیے اس الگورتھم کو عمل میں لائیں:

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 : نوڈ کی تلاش کریں، جس میں منتقلی کم از کم لاگت آئے گی۔ آپ بالکل شروع میں کھڑے ہیں اور سوچ رہے ہیں کہ کہاں جانا ہے: نوڈ A یا نوڈ B پر۔ ان میں سے ہر ایک کو پہنچنے میں کتنا وقت لگے گا؟
• مرحلہ 2 : حساب لگانا کہ B کے ان تمام پڑوسیوں تک پہنچنے میں کتنا وقت لگتا ہے جو B سے کسی کنارے پر جاتے وقت الگورتھم سے متاثر نہیں ہوئے ہیں۔ اگر یہ نیا وقت پرانے وقت سے کم نکلتا ہے، تو کنارے B سے گزرنے والا راستہ اس چوٹی کے لیے نیا مختصر ترین راستہ بن جائے گا۔
• مرحلہ 3 : نشان بی کو بطور گزرے ہوئے نشان زد کریں۔
• مرحلہ 4 : مرحلہ 1 پر جائیں۔

ہم ان مراحل کے چکر کو اس وقت تک دہرائیں گے جب تک کہ تمام چوٹیاں گزر نہ جائیں۔ آئیے درج ذیل وزنی ڈائریکٹڈ گراف پر غور کریں: لہذا، اوپر والے الگورتھم کا استعمال کرتے ہوئے، ہم A سے G تک کا مختصر ترین راستہ طے کریں گے:

1. ورٹیکس A کے لیے تین ممکنہ راستے ہیں: 3 کے وزن کے ساتھ B تک، 5 کے وزن کے ساتھ C اور 7 کے وزن کے ساتھ D تک۔ الگورتھم کے پہلے نقطہ کے مطابق، ہم سب سے کم منتقلی کے ساتھ نوڈ کا انتخاب کرتے ہیں۔ لاگت - یعنی B تک ۔
2. چونکہ B کے لیے واحد غیر متزلزل ہمسایہ ورٹیکس ہے vertex E ، ہم چیک کرتے ہیں کہ اس چوٹی سے گزرتے وقت راستہ کیا ہوگا۔ 3 ( AB ) + 6 ( BE ) = 9۔

   اس طرح، ہم نوٹ کرتے ہیں کہ AE = 9 کا موجودہ مختصر ترین راستہ۔

3. چونکہ vertex 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. ہم اس کے پڑوسی کا مختصر ترین راستہ تلاش کرتے ہیں - ایف۔

   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 میں ہمسایہ خطوط نہیں ہیں جن کی طرف ایک ہدایت شدہ راستہ لے جائے گا، ہمارے پاس صرف E vertex باقی ہے : ہم اسے منتخب کرتے ہیں۔
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²) سے زیادہ کچھ نہیں ہے کیونکہ ہمارے پاس لوپ ایک لوپ کے اندر اندر بنے ہوئے ہیں۔ ٹھیک ہے، آج میرے لیے اتنا ہی ہے، آپ کی توجہ کا شکریہ!