บทความนี้จะแนะนำอัลกอริทึม Dijkstra ที่ใช้ Java ในรูปแบบของตัวอย่าง ฉันเชื่อว่ามันจะเป็นประโยชน์สำหรับผู้อ่านในการศึกษาและเรียนรู้อัลกอริธึมโดเมนโครงสร้างข้อมูล
Dijkstra เสนออัลกอริทึมเพื่อสร้างเส้นทางที่สั้นที่สุดไปยังแต่ละจุดยอดโดยเพิ่มลำดับความยาวเส้นทางระหว่างแต่ละจุดยอดและจุดต้นทาง v นั่นคือ หาเส้นทางที่สั้นที่สุดที่มีความยาวสั้นที่สุดก่อน จากนั้นใช้เส้นทางนั้นหาเส้นทางที่สั้นที่สุดที่มีความยาวสั้นที่สุดถัดไป ไปเรื่อยๆ จนกว่าจะพบเส้นทางที่สั้นที่สุดจากจุดต้นทาง v ไปยังจุดยอดอื่นๆ
การใช้งานโค้ดมีดังนี้:
package com.algorithm.impl; public class Dijkstra { private static int M = 10,000; // ถนนนี้ถูกบล็อก static void main (String [] args) { int [] Weight1 = {// Adjacency matrix {0, 3 ,2000,7,M}, {3,0,4,2,M}, {M,4,0,5,4}, {7,2,5,0,6}, {M,M,4,6,0} }; int[][] น้ำหนัก2 = { {0,10,M,30,100}, {M,0,50,M,M}, {M,M,0, M,10}, {M,M,20,0,60}, {M,M,M,M,0} }; int[] shortPath = dijkstra(weight2,start); for(int i = 0;i < shortPath.length;i++) System.out.println("ระยะทางที่สั้นที่สุดจาก "+start+" ถึง "+i+" คือ: "+shortPath[i ] ); } สาธารณะ int [] dijkstra (int [] น้ำหนักเริ่มต้น int) { //ยอมรับเมทริกซ์น้ำหนักของกราฟกำกับและจุดเริ่มต้นหมายเลขจุดเริ่มต้น (ตัวเลขจาก 0 จุดยอดจะถูกเก็บไว้ในอาร์เรย์) //ส่งคืนอาร์เรย์ int[] ระบุความยาวของเส้นทางที่สั้นที่สุดตั้งแต่เริ่มต้นถึงมัน int n = Weight.length ; // จำนวนจุดยอด int[] shortPath = new int[n]; // บันทึกเส้นทางที่สั้นที่สุดจากจุดเริ่มต้นไปยังจุดอื่น String[] path = new String[n]; // บันทึกเส้นทางที่สั้นที่สุด เส้นทางจากจุดเริ่มต้นไปยังจุดอื่น การแสดงสตริงสำหรับ (int i=0;i<n;i++) path[i]=new String(start+"-->"+i); int[] เยี่ยมชม = new int[n]; // ทำเครื่องหมายว่าเส้นทางที่สั้นที่สุดไปยังจุดยอดปัจจุบัน ได้รับการค้นหา 1 หมายถึงพบแล้ว // การเริ่มต้นพบจุดยอดแรก shortPath [start] = 0; เยี่ยมชม [start] = 1; for (int count = 1; count < n; count ++) { // ในการเพิ่มจุดยอด n-1 int k = -1; // เลือกจุดยอดที่ไม่มีเครื่องหมายที่ใกล้กับจุดเริ่มต้นมากที่สุด int dmin = Integer.MAX_VALUE; for(int i = 0; i < n; i++) { if(visited [i] == 0 && น้ำหนัก[เริ่มต้น] < dmin) { dmin = น้ำหนัก [เริ่มต้น] [i]; //ทำเครื่องหมายจุดยอดที่เลือกใหม่ว่าเป็นเส้นทางที่สั้นที่สุดและเส้นทางที่สั้นที่สุดในการเริ่มต้นคือ dmin shortPath[k] = dmin; visit[k] = 1; //โดยให้ k เป็นจุดกึ่งกลาง ให้แก้ไขเส้นทางจาก เริ่มต้นเป็นระยะทางของจุดที่ยังไม่ได้เยี่ยมชม for(int i = 0; i < n; i++) { if(visited[i] == 0 && Weight[start][k] + Weight[k][i] < Weight[start] [ฉัน]) { น้ำหนัก [เริ่มต้น] [i] = น้ำหนัก [เริ่มต้น] [k] + น้ำหนัก [k] [i]; path [i] = เส้นทาง [k] + "-->" + i; } } } สำหรับ (int i = 0; i < n; i++) { System.out.println("เส้นทางที่สั้นที่สุดจาก "+start+" ถึง "+i+" คือ: "+path[i]); System.out.println("===================================="); กลับเส้นทางสั้น; }}ผลลัพธ์ของการรันโปรแกรมนี้คือ:
เส้นทางที่สั้นที่สุดจาก 0 ถึง 0 คือ: 0-->0 เส้นทางที่สั้นที่สุดจาก 0 ถึง 1 คือ: 0-->1 เส้นทางที่สั้นที่สุดจาก 0 ถึง 2 คือ: 0-->3-->2 จากเส้นทางที่สั้นที่สุด จาก 0 ถึง 3 คือ: 0-->3 เส้นทางที่สั้นที่สุดจาก 0 ถึง 4 คือ: 0-->3-->2-->4==== ================================== ระยะทางที่สั้นที่สุดจาก 0 ถึง 0 คือ: 0 จาก 0 ถึง 1 ระยะทางที่สั้นที่สุด จาก 0 ถึง 2 คือ: 50 ระยะทางที่สั้นที่สุดจาก 0 ถึง 3 คือ: 30 ระยะทางที่สั้นที่สุดจาก 0 ถึง 4 คือ: 60