迪杰斯特拉算法介紹

迪杰斯特拉(Dijkstra)算法是典型最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑。

它的主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展(廣度優(yōu)先搜索思想)，直到擴(kuò)展到終點(diǎn)為止。

基本思想

通過Dijkstra計(jì)算圖G中的最短路徑時(shí)，需要指定起點(diǎn)s(即從頂點(diǎn)s開始計(jì)算)。

此外，引進(jìn)兩個(gè)集合S和U。S的作用是記錄已求出最短路徑的頂點(diǎn)(以及相應(yīng)的最短路徑長度)，而U則是記錄還未求出最短路徑的頂點(diǎn)(以及該頂點(diǎn)到起點(diǎn)s的距離)。

初始時(shí)，S中只有起點(diǎn)s；U中是除s之外的頂點(diǎn)，并且U中頂點(diǎn)的路徑是"起點(diǎn)s到該頂點(diǎn)的路徑"。然后，從U中找出路徑最短的頂點(diǎn)，并將其加入到S中；接著，更新U中的頂點(diǎn)和頂點(diǎn)對應(yīng)的路徑。 然后，再從U中找出路徑最短的頂點(diǎn)，并將其加入到S中；接著，更新U中的頂點(diǎn)和頂點(diǎn)對應(yīng)的路徑。 ... 重復(fù)該操作，直到遍歷完所有頂點(diǎn)。

操作步驟

(1)?初始時(shí)，S只包含起點(diǎn)s；U包含除s外的其他頂點(diǎn)，且U中頂點(diǎn)的距離為"起點(diǎn)s到該頂點(diǎn)的距離"[例如，U中頂點(diǎn)v的距離為(s,v)的長度，然后s和v不相鄰，則v的距離為∞]。

(2)?從U中選出"距離最短的頂點(diǎn)k"，并將頂點(diǎn)k加入到S中；同時(shí)，從U中移除頂點(diǎn)k。

(3)?更新U中各個(gè)頂點(diǎn)到起點(diǎn)s的距離。之所以更新U中頂點(diǎn)的距離，是由于上一步中確定了k是求出最短路徑的頂點(diǎn)，從而可以利用k來更新其它頂點(diǎn)的距離；例如，(s,v)的距離可能大于(s,k)+(k,v)的距離。

(4)?重復(fù)步驟(2)和(3)，直到遍歷完所有頂點(diǎn)。

單純的看上面的理論可能比較難以理解，下面通過實(shí)例來對該算法進(jìn)行說明。

迪杰斯特拉算法圖解

以上圖G4為例，來對迪杰斯特拉進(jìn)行算法演示(以第4個(gè)頂點(diǎn)D為起點(diǎn))。

初始狀態(tài)：S是已計(jì)算出最短路徑的頂點(diǎn)集合，U是未計(jì)算除最短路徑的頂點(diǎn)的集合！

第1步：將頂點(diǎn)D加入到S中。

此時(shí)，S={D(0)}, U={A(∞),B(∞),C(3),E(4),F(∞),G(∞)}。 ????注:C(3)表示C到起點(diǎn)D的距離是3。

第2步：將頂點(diǎn)C加入到S中。

上一步操作之后，U中頂點(diǎn)C到起點(diǎn)D的距離最短；因此，將C加入到S中，同時(shí)更新U中頂點(diǎn)的距離。以頂點(diǎn)F為例，之前F到D的距離為∞；但是將C加入到S之后，F到D的距離為9=(F,C)+(C,D)。

此時(shí)，S={D(0),C(3)}, U={A(∞),B(23),E(4),F(9),G(∞)}。

第3步：將頂點(diǎn)E加入到S中。

上一步操作之后，U中頂點(diǎn)E到起點(diǎn)D的距離最短；因此，將E加入到S中，同時(shí)更新U中頂點(diǎn)的距離。還是以頂點(diǎn)F為例，之前F到D的距離為9；但是將E加入到S之后，F到D的距離為6=(F,E)+(E,D)。

此時(shí)，S={D(0),C(3),E(4)}, U={A(∞),B(23),F(6),G(12)}。

第4步：將頂點(diǎn)F加入到S中。

此時(shí)，S={D(0),C(3),E(4),F(6)}, U={A(22),B(13),G(12)}。

第5步：將頂點(diǎn)G加入到S中。

此時(shí)，S={D(0),C(3),E(4),F(6),G(12)}, U={A(22),B(13)}。

第6步：將頂點(diǎn)B加入到S中。

此時(shí)，S={D(0),C(3),E(4),F(6),G(12),B(13)}, U={A(22)}。

第7步：將頂點(diǎn)A加入到S中。

此時(shí)，S={D(0),C(3),E(4),F(6),G(12),B(13),A(22)}。

此時(shí)，起點(diǎn)D到各個(gè)頂點(diǎn)的最短距離就計(jì)算出來了：A(22) B(13) C(3) D(0) E(4) F(6) G(12)。

迪杰斯特拉算法的代碼說明

以"鄰接矩陣"為例對迪杰斯特拉算法進(jìn)行說明，對于"鄰接表"實(shí)現(xiàn)的圖在后面會(huì)給出相應(yīng)的源碼。

1. 基本定義

public class MatrixUDG {

private int mEdgNum; // 邊的數(shù)量

private char[] mVexs; // 頂點(diǎn)集合

private int[][] mMatrix; // 鄰接矩陣

private static final int INF = Integer.MAX_VALUE; // 最大值

...

}

MatrixUDG是鄰接矩陣對應(yīng)的結(jié)構(gòu)體。mVexs用于保存頂點(diǎn)，mEdgNum用于保存邊數(shù)，mMatrix則是用于保存矩陣信息的二維數(shù)組。例如，mMatrix[i][j]=1，則表示"頂點(diǎn)i(即mVexs[i])"和"頂點(diǎn)j(即mVexs[j])"是鄰接點(diǎn)；mMatrix[i][j]=0，則表示它們不是鄰接點(diǎn)。

2. 迪杰斯特拉算法

/*

* Dijkstra最短路徑。

* 即，統(tǒng)計(jì)圖中"頂點(diǎn)vs"到其它各個(gè)頂點(diǎn)的最短路徑。

*

* 參數(shù)說明：

* vs -- 起始頂點(diǎn)(start vertex)。即計(jì)算"頂點(diǎn)vs"到其它頂點(diǎn)的最短路徑。

* prev -- 前驅(qū)頂點(diǎn)數(shù)組。即，prev[i]的值是"頂點(diǎn)vs"到"頂點(diǎn)i"的最短路徑所經(jīng)歷的全部頂點(diǎn)中，位于"頂點(diǎn)i"之前的那個(gè)頂點(diǎn)。

* dist -- 長度數(shù)組。即，dist[i]是"頂點(diǎn)vs"到"頂點(diǎn)i"的最短路徑的長度。

*/

public void dijkstra(int vs, int[] prev, int[] dist) {

// flag[i]=true表示"頂點(diǎn)vs"到"頂點(diǎn)i"的最短路徑已成功獲取

boolean[] flag = new boolean[mVexs.length];

// 初始化

for (int i = 0; i < mVexs.length; i++) {

flag[i] = false; // 頂點(diǎn)i的最短路徑還沒獲取到。

prev[i] = 0; // 頂點(diǎn)i的前驅(qū)頂點(diǎn)為0。

dist[i] = mMatrix[vs][i]; // 頂點(diǎn)i的最短路徑為"頂點(diǎn)vs"到"頂點(diǎn)i"的權(quán)。

}

// 對"頂點(diǎn)vs"自身進(jìn)行初始化

flag[vs] = true;

dist[vs] = 0;

// 遍歷mVexs.length-1次；每次找出一個(gè)頂點(diǎn)的最短路徑。

int k=0;

for (int i = 1; i < mVexs.length; i++) {

// 尋找當(dāng)前最小的路徑；

// 即，在未獲取最短路徑的頂點(diǎn)中，找到離vs最近的頂點(diǎn)(k)。

int min = INF;

for (int j = 0; j < mVexs.length; j++) {

if (flag[j]==false && dist[j]

min = dist[j];

k = j;

}

}

// 標(biāo)記"頂點(diǎn)k"為已經(jīng)獲取到最短路徑

flag[k] = true;

// 修正當(dāng)前最短路徑和前驅(qū)頂點(diǎn)

// 即，當(dāng)已經(jīng)"頂點(diǎn)k的最短路徑"之后，更新"未獲取最短路徑的頂點(diǎn)的最短路徑和前驅(qū)頂點(diǎn)"。

for (int j = 0; j < mVexs.length; j++) {

int tmp = (mMatrix[k][j]==INF ? INF : (min + mMatrix[k][j]));

if (flag[j]==false && (tmp

dist[j] = tmp;

prev[j] = k;

}

}

}

// 打印dijkstra最短路徑的結(jié)果

System.out.printf("dijkstra(%c): \n", mVexs[vs]);

for (int i=0; i < mVexs.length; i++)

System.out.printf(" shortest(%c, %c)=%d\n", mVexs[vs], mVexs[i], dist[i]);

}

迪杰斯特拉算法的源碼

這里分別給出"鄰接矩陣圖"和"鄰接表圖"的迪杰斯特拉算法源碼。

總結(jié)

以上是生活随笔為你收集整理的简述dijkstra算法原理_Dijkstra算法之 Java详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。