สิ่งที่พวกเขาถามในการสัมภาษณ์: การทบทวนอัลกอริทึม ตอนที่ 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();
  }
}

เอาต์พุตคอนโซล: เนื่องจากเรามีเมทริกซ์ adjacency และในวิธีการเดิน เราใช้ลูปที่ซ้อนกันภายในลูป ความซับซ้อนของเวลาจะเป็น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();
  }
}

เอาต์พุตคอนโซล: อีกครั้ง: เรามีเมทริกซ์ adjacency และใช้ลูปที่ซ้อนกันภายในลูป ดังนั้นO(N²)คือความซับซ้อนของเวลาของอัลกอริทึมข้างต้น

4. อัลกอริทึมของ Dijkstra

ตามที่กล่าวไว้ข้างต้น กราฟสามารถกำหนดทิศทางหรือไม่มีการบอกทิศทางได้ และอย่างที่คุณจำได้ พวกมันยังคงสามารถชั่งน้ำหนักได้ กราฟแบบกำหนดทิศทางแบบถ่วงน้ำหนักมักพบในชีวิตจริง เช่น แผนที่ของเมือง โดยที่เมืองต่างๆ เป็นจุดยอด เส้นทางระหว่างเมืองคือถนน ถนนสามารถมีการจราจรทางเดียวได้ - ทิศทางของกราฟ สมมติว่าคุณเกี่ยวข้องกับการขนส่งสินค้า และคุณต้องสร้างเส้นทางที่สั้นที่สุดระหว่างสองเมืองที่ห่างไกล คุณจะทำเช่นนี้ได้อย่างไร? ปัญหาที่พบบ่อยที่สุดประการหนึ่งเกี่ยวกับกราฟถ่วงน้ำหนักคือปัญหาในการเลือกเส้นทางที่สั้นที่สุดระหว่างจุดยอดสองจุด เพื่อแก้ปัญหานี้ เราใช้ อัลกอริทึม ของDijkstra ฉันอยากจะทราบทันทีว่าด้วยการดำเนินการอัลกอริทึมของ 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( เอบี ) + 6( พ.ศ. ) = 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( โฆษณา ) + 3 ( DF ) = 10

7. จากจุดยอดที่ใกล้ที่สุดที่มีอยู่EและFเราเลือกจุดยอดที่มีน้ำหนักน้อยที่สุดของขอบนั่นคือF (3)
8. เราค้นหาเส้นทางที่สั้นที่สุดไปยังเพื่อนบ้าน- G.

   เอจี = 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 ) ถึงเวลาที่จะดูว่าสิ่งนี้สามารถนำไปใช้ใน Java ได้อย่างไร ก่อนอื่น มาดูคลาสจุดสุดยอดกันก่อน:

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²)เนื่องจากเรามีลูปซ้อนกันภายในลูป นั่นคือทั้งหมดสำหรับฉันในวันนี้ ขอบคุณสำหรับความสนใจของคุณ!