迪杰斯特拉(Dijkstra)算法是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959年提出的。是尋找從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，可用來(lái)解決最短路徑問(wèn)題。
迪杰斯特拉算法采用貪心算法的策略，將所有頂點(diǎn)分為已標(biāo)記點(diǎn)和未標(biāo)記點(diǎn)兩個(gè)集合，從起始點(diǎn)開(kāi)始，不斷在未標(biāo)記點(diǎn)中尋找距離起始點(diǎn)路徑最短的頂點(diǎn)，并將其標(biāo)記，直到所有頂點(diǎn)都被標(biāo)記為止。需要注意的一點(diǎn)是該方法不能處理帶有負(fù)權(quán)邊的圖，下面我們舉出一個(gè)實(shí)例并通過(guò)迪杰斯特拉方法對(duì)其進(jìn)行求解。
圖1所示為一個(gè)最短路徑問(wèn)題，每條邊代表一條路徑，邊上的數(shù)值表示這條邊的長(zhǎng)度。
我們用迪杰斯特拉方法尋找從頂點(diǎn)0到頂點(diǎn)5的最短路徑。標(biāo)號(hào)結(jié)果如圖2所示，圖中括號(hào)里的兩個(gè)數(shù)分別表示該點(diǎn)的父頂點(diǎn)標(biāo)號(hào)和初始點(diǎn)到該點(diǎn)的最短路徑長(zhǎng)度。由圖2可知，從節(jié)點(diǎn)0到節(jié)點(diǎn)5的最短路徑長(zhǎng)度為9，最短路徑為：0 -> 2 -> 3 -> 5。
下面我們考慮通過(guò)java語(yǔ)言來(lái)實(shí)現(xiàn)用迪杰斯特拉算法尋找圖一中的頂點(diǎn)0到頂點(diǎn)5的最短路徑問(wèn)題。
我們首先創(chuàng)建一個(gè)頂點(diǎn)類(lèi)，屬性包括id、父點(diǎn)和到起始點(diǎn)的最短距離。主方法主要分為五個(gè)部分，在第一部分進(jìn)行數(shù)據(jù)的初始化；第二個(gè)部分新建一個(gè)已標(biāo)記點(diǎn)集合，創(chuàng)建一個(gè)點(diǎn)對(duì)象作為起始頂點(diǎn)加入到已標(biāo)記點(diǎn)集合中；第二部分新建一個(gè)未標(biāo)記點(diǎn)集合，創(chuàng)建其余5個(gè)點(diǎn)并添加到未標(biāo)記點(diǎn)集合中；第三部分為一個(gè)while循環(huán)，功能是不斷的將未標(biāo)記點(diǎn)集合中的點(diǎn)轉(zhuǎn)移到已標(biāo)記點(diǎn)集合中去；第五部分是路徑的輸出。在第四部分，每個(gè)循環(huán)中我們需要尋找要進(jìn)行標(biāo)記的頂點(diǎn)，因此我們創(chuàng)建了一個(gè)尋找要標(biāo)記頂點(diǎn)的函數(shù)，其功能是在所有未標(biāo)記點(diǎn)中尋找距離起始頂點(diǎn)距離最短的頂點(diǎn)，具體過(guò)程如下：
初始時(shí)，已標(biāo)記點(diǎn)集合中只有源節(jié)點(diǎn)，未標(biāo)記點(diǎn)集合中包含剩余所有節(jié)點(diǎn)。隨后進(jìn)入迭代，每次迭代時(shí)，首先探索從已標(biāo)記節(jié)點(diǎn)（如vi）流出的所有有向弧，找到流出弧的尾部節(jié)點(diǎn)（如vj），計(jì)算從vi到vj的費(fèi)用和收益以及到源節(jié)點(diǎn)的利潤(rùn)（vj到源節(jié)點(diǎn)的利潤(rùn)=vi到源節(jié)點(diǎn)的利潤(rùn)+vi到vj的利潤(rùn)），若該利潤(rùn)大于vj到源節(jié)點(diǎn)的最大利潤(rùn)，將vj到源節(jié)點(diǎn)的最大利潤(rùn)更新為該利潤(rùn)，將vi標(biāo)記為vj的上一個(gè)節(jié)點(diǎn)。未標(biāo)記點(diǎn)集合遍歷完成后，若節(jié)點(diǎn)vj滿足在所有未標(biāo)記點(diǎn)中到源節(jié)點(diǎn)的利潤(rùn)最大，將節(jié)點(diǎn)vj添加到已標(biāo)記點(diǎn)集合，并在未標(biāo)記點(diǎn)集合中刪除節(jié)點(diǎn)vj。
不斷重復(fù)上述操作，直至未標(biāo)記點(diǎn)集合為空集。迪杰斯特拉算法就是將所有頂點(diǎn)分為已標(biāo)記點(diǎn)和未標(biāo)記點(diǎn)兩個(gè)集合，從起始點(diǎn)開(kāi)始，不斷在未標(biāo)記點(diǎn)中尋找距離起始點(diǎn)利潤(rùn)最大的節(jié)點(diǎn)，并將其標(biāo)記，直到所有頂點(diǎn)都被標(biāo)記為止。詳細(xì)代碼如下：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-533071.html
import java.util.ArrayList;
import java.util.List;
public class Dijkstra {
static int[][] matrix = new int[6][6];
final static int N = 10000;
public static void main(String[] args) {
//鄰接矩陣
matrix[0] = new int[]{0, 6, 3, N, N, N};/*1*/
matrix[1] = new int[]{6, 0, 2, 5, N, N};/*2*/
matrix[2] = new int[]{3, 2, 0, 3, 4, N};/*3*/
matrix[3] = new int[]{N, 5, 3, 0, 2, 3};/*4*/
matrix[4] = new int[]{N, N, 4, 2, 0, 5};/*5*/
matrix[5] = new int[]{N, N, N, 3, 5, 0};/*6*/
//已標(biāo)記點(diǎn)集合
List<Vertex> Marked = new ArrayList<>();
Vertex vt0 = new Vertex();
vt0.id = 0;
vt0.minLenth = 0;
Marked.add(vt0);
//未標(biāo)記點(diǎn)集合
List<Vertex> UnMarked = new ArrayList<>();
for (int i = 0; i < 5; i++) {
Vertex vtx = new Vertex();
vtx.id = i+1;
UnMarked.add(vtx);
}
//將未標(biāo)記點(diǎn)集合中的點(diǎn)轉(zhuǎn)移到已標(biāo)記點(diǎn)集合
int order = 1;
while(!UnMarked.isEmpty()){
Vertex vtx = FindVer(Marked, UnMarked);
UnMarked.remove(vtx);
Marked.add(vtx);
System.out.println("第"+order+"次標(biāo)號(hào)，頂點(diǎn)"+vtx.id+"的標(biāo)號(hào)為：（" + vtx.father.id + "，" +vtx.minLenth + "）");
order++;
}
//輸出路徑
for(Vertex v :Marked){
if(v.id == 5){
System.out.println("0-5的最短路徑長(zhǎng)度為：" + v.minLenth);
System.out.print("逆推得最優(yōu)路徑為：" + "5");
while(v.id != 0){
v = v.father;
System.out.print( " -> " + v.id);
}
}
}
}
static Vertex FindVer(List<Vertex> Marked, List<Vertex> UnMarked){
int M = 10000;
Vertex v = null;
for (Vertex ve : UnMarked) {
for (Vertex vr : Marked) {
int all_p = vr.minLenth + matrix[vr.id][ve.id];
if (all_p <= ve.minLenth) {
ve.minLenth = all_p;
ve.father = vr;
}
}
if (ve.minLenth < M) {
M = ve.minLenth;
v = ve;
}
}
return v;
}
}
class Vertex {
public int id;
public Vertex father;
public int minLenth = 10000;
}
程序的運(yùn)行結(jié)果如下：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-533071.html
第1次標(biāo)號(hào)，頂點(diǎn)2的標(biāo)號(hào)為：（0，3）
第2次標(biāo)號(hào)，頂點(diǎn)1的標(biāo)號(hào)為：（2，5）
第3次標(biāo)號(hào)，頂點(diǎn)3的標(biāo)號(hào)為：（2，6）
第4次標(biāo)號(hào)，頂點(diǎn)4的標(biāo)號(hào)為：（2，7）
第5次標(biāo)號(hào)，頂點(diǎn)5的標(biāo)號(hào)為：（3，9）
0-5的最短路徑長(zhǎng)度為：9
逆推得最優(yōu)路徑為：5 -> 3 -> 2 -> 0
進(jìn)程已結(jié)束,退出代碼0到了這里，關(guān)于java實(shí)現(xiàn)迪杰斯特拉(Dijkstra)算法求解最短路問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
