Artikel ini memperkenalkan algoritma Dijkstra berbasis Java dalam bentuk contoh. Saya yakin akan membantu pembaca dalam mempelajari dan mempelajari algoritma domain struktur data.
Dijkstra mengusulkan suatu algoritma untuk menghasilkan jalur terpendek ke setiap titik dengan urutan pertambahan panjang jalur antara setiap titik dan titik sumber v. Artinya, pertama-tama cari jalur terpendek dengan panjang terpendek, lalu gunakan untuk mencari jalur terpendek dengan panjang terpendek berikutnya, dan seterusnya hingga semua jalur terpendek dari titik sumber v ke simpul lain ditemukan.
Implementasi kodenya adalah sebagai berikut:
paket com.algorithm.impl; public class Dijkstra { private static int M = 10000; //Jalan ini diblokir public static void main(String[] args) { int[][] bobot1 = {//Matriks ketetanggaan {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[][] berat2 = { {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 mulai=0; int[] jalur pendek = dijkstra(weight2,start); for(int i = 0;i < shortPath.length;i++) System.out.println("Jarak terpendek dari "+start+" ke "+i+" adalah: "+shortPath[i ] ); } publik statis int[] dijkstra(int[][] berat, int mulai) { //Menerima matriks bobot dari graf berarah, dan nomor titik awal permulaan (diberi nomor dari 0, simpul disimpan dalam larik) //Mengembalikan larik int[], yang menunjukkan panjang jalur terpendek dari awal hingga larik tersebut int n = berat.panjang ; //Jumlah simpul int[] shortPath = new int[n]; //Simpan jalur terpendek dari awal ke titik lainnya String[] path = new String[n]; jalur dari awal ke titik lain Representasi string untuk(int i=0;i<n;i++) path[i]=new String(start+"-->"+i); int[] yang dikunjungi = new int[n]; //Tandai apakah jalur terpendek ke titik saat ini telah Temukan, 1 berarti telah ditemukan //Inisialisasi, simpul pertama telah ditemukan shortPath[mulai] = 0; dikunjungi[mulai] = 1; for(int count = 1; count < n; count++) { //Untuk menjumlahkan n-1 simpul int k = -1; //Pilih simpul tak bertanda yang paling dekat dengan simpul awal start int dmin = Integer.MAX_VALUE; for(int i = 0; i < n; i++) { if(visited [i] == 0 && berat[mulai][i] < dmin) { dmin = berat[mulai][i]; //Tandai simpul yang baru dipilih sebagai jalur terpendek telah ditemukan, dan jalur terpendek untuk memulai adalah dmin shortPath[k] = dmin yang dikunjungi[k] = 1; //Dengan k sebagai titik tengah, perbaiki jalur dari mulai Jarak titik yang belum dikunjungi for(int i = 0; i < n; i++) { if(visited[i] == 0 && berat[mulai][k] + berat[k][i] < berat[mulai] [Saya]) { berat[mulai][i] = berat[mulai][k] + berat[k][i]; jalur[i] = jalur[k] + "-->" + i; 0; i < n; i++) { System.out.println("Jalur terpendek dari "+start+" ke "+i+" adalah: "+path[i] } System.out.println("========== "); kembalikan shortPath; }}Hasil dari menjalankan program ini adalah:
Jalur terpendek dari 0 ke 0 adalah: 0-->0 Jalur terpendek dari 0 ke 1 adalah: 0-->1 Jalur terpendek dari 0 ke 2 adalah: 0-->3-->2 dari Jalur terpendek dari 0 ke 3 adalah: 0-->3 Jalur terpendek dari 0 ke 4 adalah: 0-->3-->2-->4==== ==================Jarak terpendek dari 0 ke 0 adalah: 0 dari 0 ke 1 Jarak terpendek dari 0 ke 2 adalah: 50 Jarak terpendek dari 0 ke 3 adalah: 30 Jarak terpendek dari 0 ke 4 adalah: 60