Он чизе ки онҳо дар мусоҳиба мепурсанд: баррасии алгоритмҳо, қисми 2

Ин мақола идомаи баррасии кӯтоҳи ман дар бораи алгоритмҳост. Ин аст пайванд ба қисми аввал . Пештар, мо алгоритмҳои ҷудокунии массивҳо ва ба истилоҳ алгоритми хасисро дида баромадем . Имрӯз мо дар бораи графикҳо ва алгоритмҳои марбут ба онҳо сӯҳбат хоҳем кард. Графика яке аз сохторҳои чандиртарин ва универсалӣ дар барномасозӣ мебошад. Графикаи G одатан бо истифода аз ҷуфти маҷмӯи G = (V, R) муайян карда мешавад , ки дар он ҷо:

• V маҷмӯи қуллаҳо мебошад;
• R маҷмӯи хатҳоест, ки ҷуфтҳои қуллаҳоро мепайвандад.

Хатҳои пайвасткунандаи умумӣ кунҷҳо номида мешаванд : Хатҳои дорои тирчаҳо - камонҳо : Одатан, график бо истифода аз диаграммае тасвир карда мешавад, ки дар он баъзе қуллаҳо бо кунҷҳо (камонҳо) пайваст карда мешаванд. Графикаҳое, ки бо камонҳо ба ҳамдигар пайваст мешаванд, ки самтро мустақиман нишон медиҳанд, равона карда мешаванд . Агар графикҳо бо кунҷҳо пайваст карда шаванд, яъне бе нишон додани самти ҳаракати эҳтимолӣ, онҳо бесамар мешаванд . Ин маънои онро дорад, ки ҳаракат дар баробари онҳо дар ҳар ду самт имконпазир аст: ҳам аз қуллаи А то В ва ҳам аз В то А. Графикаи пайваст графикест, ки дар он ҳадди аққал як роҳ аз ҳар як қулла ба ягон қуллаи дигар мебарад (чунон ки дар мисол). боло). Агар ин тавр набошад, график ҷудо мешавад : Инчунин, кунҷҳо (камонҳо) метавонанд вазнҳо таъин карда шаванд - рақамҳое, ки масофаи физикии байни ду қулларо (ё вақти нисбии гузариш байни ду қулларо) намояндагӣ мекунанд. Чунин графикҳо вазннок номида мешаванд :

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

Натиҷаи консол: Азбаски мо матритсаи ҳамсоя дорем ва дар усули роҳ мо ҳалқаеро истифода мебарем, ки дар дохor як ҳалқа ҷойгир шудааст, мураккабии вақт O(N²) хоҳад буд .

Хишти васеъ

Ин алгоритм, ба монанди гузариши умқи аввал, яке аз соддатарин ва асосӣтарин усулҳои убури график мебошад. Моҳияти он дар он аст, ки мо як қуллаи муайяни ҷорӣ дорем, ки аз он мо ҳама қуллаҳои ҳамшафати ногузарро ба навбат мегузорем ва элементи навбатиро (ки дар навбат нигоҳ дошта мешавад) интихоб мекунем, то он ҷорӣ шавад... Агар ин алгоритмро ба Дар марҳилаҳо, мо метавонем қоидаҳои зеринро қайд кунем:

1. Ба қуллаи навбатӣ, ки қаблан боздиднашуда дар шафати қуллаи ҷорӣ дидан кунед, онро пешакӣ қайд кунед ва ба навбат илова кунед.
2. Агар қоидаи №1 иҷро нашавад, қулларо аз навбат хориҷ кунед ва онро ба қуллаи ҷорӣ созед.
3. Агар қоидаҳои №1 ва №2 ғайриимкон бошад, гузаргоҳ ба анҷом мерасад ва ҳамаи қуллаҳо гузаштанд (агар графики мо пайваст бошад).

Синфи график тақрибан ба синфи шабеҳи алгоритми ҷустуҷӯи умқи аввал шабеҳ аст, ба истиснои усуле, ки алгоритмро коркард мекунад ва стеки дохorро бо навбат иваз мекунад:

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

Натиҷаи консол: Боз: мо матритсаи ҳамсоя дорем ва ҳалқаеро, ки дар дохor як ҳалқа ҷойгир шудааст, истифода мебарем, аз ин рӯ O(N²) мураккабии вақти алгоритми боло аст.

4. Алгоритми Дийкстра

Тавре ки дар боло зикр гардид, графикҳо метавонанд равона ё беасос бошанд . Ва чунон ки шумо дар хотир доред, онҳо ҳоло ҳам вазн карда метавонанд . Графикҳои вазннок, равонашуда аксар вақт дар ҳаёти воқеӣ пайдо мешаванд: масалан, харитаи шаҳрҳо, ки дар он шаҳрҳо қуллаҳо мебошанд, пайраҳаҳои байни онҳо роҳҳо мебошанд, роҳҳо метавонанд ҳаракати яктарафа дошта бошанд - самти график. Фарз мекунем, ки шумо бо ҳамлу нақли бор машғулед ва ба шумо лозим аст, ки роҳи кӯтоҳтаринро байни ду шаҳри дур созед. Шумо ин корро чӣ тавр мекунед? Яке аз мушкилоти маъмултарин бо графикҳои вазннок ин масъалаи интихоби кӯтоҳтарин роҳи байни ду қулла мебошад. Барои ҳалли ин масъала мо алгоритми Dijkstra-ро истифода мебарем . Дарҳол қайд кардан мехоҳам, ки бо иҷрои алгоритми Дийкстра мо роҳи кӯтоҳтаринро ба ҳама қуллаҳо аз як ибтидои додашуда меёбем. Ин алгоритм кадом марҳилаҳоро дорад? Ман кӯшиш мекунам, ки ба ин савол ҷавоб диҳам. Қадамҳои алгоритми Dijkstra:

• Марҳилаи 1 : Ҷустуҷӯи гиреҳ, ки гузариш ба он арзиши камтарин хоҳад буд. Шумо дар ибтидо истода, дар ҳайрат ҳастед, ки ба куҷо равед: ба гиреҳи А ё ба гиреҳи В. Барои расидан ба ҳар яке аз ин гиреҳҳо чӣ қадар вақт лозим аст?
• Марҳилаи 2 : ҳисоб кардани он, ки барои расидан ба ҳамаи ҳамсояҳои В , ки ҳангоми ҳаракат дар канори канори B то ҳол аз алгоритм таъсир нагирифтаанд , чӣ қадар вақт лозим аст. Агар ин вақти нав аз вақти кӯҳна камтар шавад, роҳ аз канори B роҳи нави кӯтоҳтарин барои ин қулла мешавад.
• Марҳилаи 3 : қуллаи В-ро ҳамчун гузашта қайд кунед.
• Қадами 4 : Ба Қадами 1 гузаред.

Мо давраҳои ин марҳилаҳоро такрор мекунем, то он даме, ки ҳамаи қуллаҳо гузаштанд. Биёед графики вазншудаи зеринро дида бароем: Ҳамин тавр, бо истифода аз алгоритми дар боло овардашуда мо роҳи кӯтоҳтаринро аз А то G муайян мекунем:

1. Барои қуллаи А се роҳи имконпазир вуҷуд дорад: ба B бо вазни 3, ба C бо вазни 5 ва ба D бо вазни 7. Мувофиқи нуқтаи аввали алгоритм, гиреҳро бо гузариши пасттарин интихоб мекунем. арзиш — яъне ба Б.
2. Азбаски ягона қуллаи ҳамсояи ногузар барои B қуллаи E аст , мо месанҷем, ки ҳангоми гузаштан аз ин қулла чӣ роҳ хоҳад буд. 3( AB ) + 6( BE ) = 9.

   Ҳамин тариқ, мо қайд мекунем, ки роҳи кӯтоҳтарин ба AE = 9.

3. Азбаски кори мо бо қуллаи 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

   Воқеан, мо дар ин ҷо роҳро аз А то Г ёфтем.

   Аммо барои боварӣ ҳосил кардани он, ки он кӯтоҳтарин аст, мо бояд қадамҳои худро барои вертекси E низ иҷро кунем .

9. Азбаски қуллаи G қуллаҳои ҳамсоя надорад, ки роҳи равонашуда ба онҳо мебарад, мо танҳо қуллаи E боқӣ мондаем : мо онро интихоб мекунем.
10. Мо рохи кутохтаринро ба суи хамсоя — Г.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, ин роҳ аз кӯтоҳтарин AG(14) дарозтар аст, бинобар ин мо ин роҳро бетағйир мегузорем.

    Азбаски ягон қуллаҳои пеш аз G мавҷуд нестанд , иҷро кардани марҳилаҳо барои қуллаи додашуда маъно надорад. Аз ин рӯ, кори алгоритмро пурра ҳисоб кардан мумкин аст.

Тавре ки ман қаблан гуфта будам, ба ғайр аз ёфтани роҳи кӯтоҳтарин барои AG , мо роҳҳои кӯтоҳтаринро ба ҳама қуллаҳо аз қуллаи A (AB, AC, AD, AE, AF) гирифтем . Хуб, вақти он расидааст, ки бубинем, ки ин корро дар Java чӣ гуна амалӣ кардан мумкин аст. Аввалан, биёед ба синфи vertex назар андозем:

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

Ва натиҷа дар консол: Мушкorи вақти ин алгоритм чизе бештар аз O(N²) нест , зеро мо ҳалқаҳоро дар дохor як ҳалқа ҷойгир кардаем. Хуб, ин ҳама барои ман имрӯз аст, ташаккур барои таваҷҷӯҳатон!