快捷導(dǎo)航

詳解Java中Dijkstra(迪杰斯特拉)算法的圖解與實(shí)現(xiàn)

更新時(shí)間：2022年05月20日 15:56:03 作者：Carol

Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計(jì)算一個節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。本文將詳解該算法的圖解與實(shí)現(xiàn)，需要的可以參考一下

簡介

Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計(jì)算一個節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。注意該算法要求圖中不存在負(fù)權(quán)邊。對應(yīng)問題：在無向圖G=(V,E)中，假設(shè)每條邊E(i)的長度W(i)，求由頂點(diǎn)V0到各節(jié)點(diǎn)的最短路徑。

工作過程

Dijkstra算法將頂點(diǎn)集合分為兩組，一組記錄已經(jīng)求得最短路徑的頂點(diǎn)記為finallyNodes，一組正在求解中的頂點(diǎn)記為processNodes，step1:finallyNodes中頂點(diǎn)最開始只有源節(jié)點(diǎn)，最短路徑長度為0，而processNodes中包含除源節(jié)點(diǎn)以外的節(jié)點(diǎn)，并初始化路徑長度，與源節(jié)點(diǎn)直接相連的記路徑長度為權(quán)重，不相連的記為∞。step2:從process中選擇路徑長度最小的頂點(diǎn)，加入finallyNodes，并且更新processNodes，將與當(dāng)前頂點(diǎn)相連的頂點(diǎn)路徑長度更新為min（當(dāng)前權(quán)重，當(dāng)前頂點(diǎn)最短路徑長度+當(dāng)前頂點(diǎn)與頂點(diǎn)相連邊權(quán)重）。step3:重復(fù)step2，直至processNodes數(shù)組為空。

總體思路

這次我想先描述一下自己的大概思路，下面再寫具體實(shí)現(xiàn)。首先為了方便，我采用的是鄰接表存儲圖結(jié)構(gòu)，鄰接表是一個二維數(shù)組，值存儲權(quán)重。根據(jù)上面工作過程中描述的內(nèi)容，我們會有兩個中間集合記錄，finallyNodes記錄的是最終結(jié)果，我們只需要將計(jì)算的結(jié)果往里面塞即可。但是processNodes卻是一個不斷變化更新的集合，其中的操作包括刪除節(jié)點(diǎn)，更改節(jié)點(diǎn)值，查找節(jié)點(diǎn)值，同時(shí)我們每次需要拿出processNodes中記錄的距離最小的值，所以ProcessNodes準(zhǔn)備用最小堆來做，那再刪除節(jié)點(diǎn)，更改節(jié)點(diǎn)值之后都需要調(diào)整堆為最小堆，java自帶的優(yōu)先隊(duì)列沒有提供更改節(jié)點(diǎn)值的操作，因此我們這里需要自己實(shí)現(xiàn)一個小根堆，支持以上操作。然后就中規(guī)中矩實(shí)現(xiàn)dijkstra算法即可。

實(shí)現(xiàn)

小根堆

如果對堆不太熟悉的可以先看看這篇文章：堆（優(yōu)先隊(duì)列），這里就不過多解釋了，直接貼代碼。這里堆中存的數(shù)據(jù)格式為int二維數(shù)組,存儲節(jié)點(diǎn)下標(biāo)位置和對應(yīng)距離，排序按存儲的距離進(jìn)行排序。

public?class?MinHeap?{
? ? ? ?List<int[][]>?heap?;
? ? ? ?/**
? ? ? ??* 獲取并移除堆頂元素，并調(diào)整堆
? ? ? ??* @return
? ? ? ??*/
? ? ? ?public?int[][]?pop() {
? ? ? ? ? ?int[][]?top?=?heap.get(0);
? ? ? ? ? ?heap.set(0,?heap.get(heap.size()?-?1));
? ? ? ? ? ?heap.remove(heap.size()?-?1);
? ? ? ? ? ?//調(diào)整堆
? ? ? ? ? ?this.adjust(0,?heap.size()?-?1);
? ? ? ? ? ?return?top;
? ? ? }

? ? ? ?/**
? ? ? ??* 判斷是否為空
? ? ? ??* @return true/false
? ? ? ??*/
? ? ? ?public?boolean?isEmpty() {
? ? ? ? ? ?if?(null?==?this.heap) {
? ? ? ? ? ? ? ?return?true;
? ? ? ? ? }
? ? ? ? ? ?if?(this.heap.size()?==?0) {
? ? ? ? ? ? ? ?return?true;
? ? ? ? ? }
? ? ? ? ? ?return?false;
? ? ? }
? ? ? ?/**
? ? ? ??* 修改index位置節(jié)點(diǎn)的value值，并調(diào)整最小堆（Java priorityQueue未提供）
? ? ? ??* @param index 修改節(jié)點(diǎn)位置
? ? ? ??* @param value 修改值
? ? ? ??*/
? ? ? ?public?void?changeValue(int?index,?int?value) {
? ? ? ? ? ?int?src?=?heap.get(index)[0][1];
? ? ? ? ? ?heap.get(index)[0][1]?=?value;
? ? ? ? ? ?//直接比較當(dāng)前值是變大還是變小,然后考慮是向上調(diào)整還是向下調(diào)整
? ? ? ? ? ?//則當(dāng)前值可能往上移動
? ? ? ? ? ?if?(src?>?value) {
? ? ? ? ? ? ? ?this.upAdjust(index);
? ? ? ? ? ? ? ?return;
? ? ? ? ? }
? ? ? ? ? ?this.adjust(index,?heap.size()?-?1);
? ? ? }

? ? ? ?public?void?upAdjust(int?index) {
? ? ? ? ? ?//依次與雙親節(jié)點(diǎn)進(jìn)行比較，小于雙親節(jié)點(diǎn)就直接交換。一直到根節(jié)點(diǎn)
? ? ? ? ? ?while?(index?>?0) {
? ? ? ? ? ? ? ?int?parent?=?index?>>?1;
? ? ? ? ? ? ? ?//雙親節(jié)點(diǎn)本來小于當(dāng)前節(jié)點(diǎn)不需要進(jìn)行調(diào)整
? ? ? ? ? ? ? ?if?(heap.get(parent)[0][1]?<=?heap.get(index)[0][1]) {
? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?swap(index,?parent);
? ? ? ? ? ? ? ?index?=?parent;
? ? ? ? ? }
? ? ? }
? ? ? ?
? ? ? ?/**
? ? ? ??* 初始化一個最小堆
? ? ? ??* @param nums
? ? ? ??*/
? ? ? ?public?void?init(int[][]?nums) {
? ? ? ? ? ?heap?=?new?ArrayList<>(nums.length);
? ? ? ? ? ?for?(int?i?=?0?;?i?<?nums.length;?i?++) {
? ? ? ? ? ? ? ?int[][]?temp?=?new?int[1][2];
? ? ? ? ? ? ? ?temp[0][0]?=?nums[i][0];
? ? ? ? ? ? ? ?temp[0][1]?=?nums[i][1];
? ? ? ? ? ? ? ?heap.add(temp);
? ? ? ? ? }
? ? ? ? ? ?//從最后一個雙親節(jié)點(diǎn)開始將堆進(jìn)行調(diào)整
? ? ? ? ? ?for?(int?i?=?nums.length?/?2?;?i?>=?0?;?--?i) {
? ? ? ? ? ? ? ?this.adjust(i,?nums.length?-?1);
? ? ? ? ? }
? ? ? }
? ? ? ?/**
? ? ? ??* 從當(dāng)前index開始調(diào)節(jié)為最小堆
? ? ? ??* @param index 當(dāng)前節(jié)點(diǎn)下標(biāo)
? ? ? ??* @param end 最后一個節(jié)點(diǎn)下標(biāo)
? ? ? ??*/
? ? ? ?private?void?adjust(int?index,?int?end) {
? ? ? ? ? ?//找到當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)，將較小的節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)交換，一直往下，直至end
? ? ? ? ? ?while?(index?<=?end) {
? ? ? ? ? ? ? ?//左孩子節(jié)點(diǎn)
? ? ? ? ? ? ? ?int?left?=?index?<<?1;
? ? ? ? ? ? ? ?if?(left?+?1?<=?end?&&?heap.get(left?+?1)[0][1]?<?heap.get(left)[0][1] ) {
? ? ? ? ? ? ? ? ? ?//找到當(dāng)前較小的節(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ?++?left;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?//沒有孩子節(jié)點(diǎn)，或者當(dāng)前的孩子節(jié)點(diǎn)均已大于當(dāng)前節(jié)點(diǎn)，已符合最小堆，不需要進(jìn)行調(diào)整
? ? ? ? ? ? ? ?if?(left?>?end?||?heap.get(index)[0][1]?<=?heap.get(left)[0][1]) {
? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?swap(index,?left);
? ? ? ? ? ? ? ?index?=?left;
? ? ? ? ? }
? ? ? }
? ? ? ?private?void?swap(int?i,?int?j) {
? ? ? ? ? ?int[][]?temp?=?heap.get(i);
? ? ? ? ? ?heap.set(i,?heap.get(j));
? ? ? ? ? ?heap.set(j,?temp);
? ? ? }
? }

Dijsktra

數(shù)據(jù)結(jié)構(gòu)

圖節(jié)點(diǎn)僅存儲節(jié)點(diǎn)值，一個Node數(shù)組nodes，存儲圖中所有節(jié)點(diǎn)，一個二維數(shù)組adjacencyMatrix，存儲圖中節(jié)點(diǎn)之間邊的權(quán)重，行和列下標(biāo)與nodes數(shù)組下標(biāo)對應(yīng)。

//節(jié)點(diǎn)
Node[]?nodes;

//鄰接矩陣
int[][]?adjacencyMatrix;
public?class?Node?{
? ? ? ?private?char?value;
? ? ? ?Node(char?value) {
? ? ? ? ? ?this.value?=?value;
? ? ? }
? }

初始化

初始化圖values標(biāo)志的圖中所有節(jié)點(diǎn)值，edges標(biāo)志圖中邊，數(shù)據(jù)格式為（node1的下標(biāo)，node2的下標(biāo)，邊權(quán)重）

private?void?initGraph(char[]?values,?String[]?edges) {
? ? ? ?nodes?=?new?Node[values.length];
//初始化node節(jié)點(diǎn)
? ? ? ?for?(int?i?=?0?;?i?<?values.length?;?i?++) {
? ? ? ? ? ?nodes[i]?=?new?Node(values[i]);
? ? ? }
? ? ? ?adjacencyMatrix?=?new?int[values.length][values.length];
//初始化鄰接表，同一個節(jié)點(diǎn)權(quán)重記為0，不相鄰節(jié)點(diǎn)權(quán)重記為Integer.MAX_VALUE
? ? ? ?for?(int?i?=?0?;?i?<?values.length?;?i++) {
? ? ? ? ? ?for?(int?j?=?0?;?j?<?values.length?;?j?++) {
? ? ? ? ? ? ? ?if?(i?==?j) {
? ? ? ? ? ? ? ? ? ?adjacencyMatrix[i][j]?=?0;
? ? ? ? ? ? ? ? ? ?continue;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?adjacencyMatrix[i][j]?=?Integer.MAX_VALUE;
? ? ? ? ? ? ? ?adjacencyMatrix[j][i]?=?Integer.MAX_VALUE;
? ? ? ? ? }
? ? ? }
//根據(jù)edges更新相鄰節(jié)點(diǎn)權(quán)重值
? ? ? ?for?(String?edge?:?edges) {
? ? ? ? ? ?String[]?node?=?edge.split(",");
? ? ? ? ? ?int?i?=?Integer.valueOf(node[0]);
? ? ? ? ? ?int?j?=?Integer.valueOf(node[1]);
? ? ? ? ? ?int?weight?=?Integer.valueOf(node[2]);
? ? ? ? ? ?adjacencyMatrix[i][j]?=?weight;
? ? ? ? ? ?adjacencyMatrix[j][i]?=?weight;
? ? ? }
? ? ? ?visited?=?new?boolean[nodes.length];

? }

初始化dijsktra算法必要的finallyNodes和processNodes

/**
* 標(biāo)志對應(yīng)下標(biāo)節(jié)點(diǎn)是否已經(jīng)處理，避免二次處理
*/
boolean[]?visited;
? ?/**
? ??* 記錄已經(jīng)求得的最短路徑 finallyNodes[0][0]記錄node下標(biāo)，finallyNodes[0][1]記錄最短路徑長度
? ??*/
? ?List<int[][]>?finallyNodes;
? ?/**
? ??* 記錄求解過程目前的路徑長度，因?yàn)槊看稳‘?dāng)前已知最短，所以最小堆進(jìn)行記錄
? ??* 但是java優(yōu)先隊(duì)列沒有實(shí)現(xiàn)改變值，這里需要自己實(shí)現(xiàn)
? ??* 首先每次取出堆頂元素之后，堆頂元素加入finallyNodes，此時(shí)需要更新與當(dāng)前元素相鄰節(jié)點(diǎn)的路徑長度
? ??* 然后重新調(diào)整小根堆
? ??* 首先：只會更新變小的數(shù)據(jù)，所以從變小元素開始往上進(jìn)行調(diào)整，或者直接調(diào)用調(diào)整方法，從堆頂往下進(jìn)行調(diào)整
? ??*/
? ?MinHeap?processNodes;
/**
? ??* 初始化，主要初始化finallyNodes和processNodes，finallyNodes加入源節(jié)點(diǎn)，processNodes加入其他節(jié)點(diǎn)
? ??* @param nodeIndex
? ??*/
? ?private?void?initDijkstra(int?nodeIndex) {
? ? ? ?finallyNodes?=?new?ArrayList<>(nodes.length);
? ? ? ?processNodes?=?new?MinHeap();
? ? ? ?int[][]?node?=?new?int[1][2];
? ? ? ?node[0][0]?=?nodeIndex;
? ? ? ?node[0][1]?=?adjacencyMatrix[nodeIndex][nodeIndex];
? ? ? ?finallyNodes.add(node);
? ? ? ?visited[nodeIndex]?=?true;
? ? ? ?int[][]?process?=?new?int[nodes.length?-?1][2];
? ? ? ?int?j?=?0;
? ? ? ?for?(int?i?=?0?;?i?<?nodes.length?;?i++) {
? ? ? ? ? ?if?(i?==?nodeIndex) {
? ? ? ? ? ? ? ?continue;
? ? ? ? ? }
? ? ? ? ? ?process[j][0]?=?i;
? ? ? ? ? ?process[j][1]?=?adjacencyMatrix[nodeIndex][i];
? ? ? ? ? ?++?j;
? ? ? }
? ? ? ?//初始化最小堆
? ? ? ?processNodes.init(process);
? }

dijsktra算法實(shí)現(xiàn)

public?void?dijkstra() {
? ? ? ?//1。堆頂取出最小元素，加入finallyNodes
//2。將與堆頂元素相連節(jié)點(diǎn)距離更新，
? ? ? ?while?(!processNodes.isEmpty()) {
? ? ? ? ? ?int[][]?head?=?processNodes.pop();
? ? ? ? ? ?finallyNodes.add(head);
? ? ? ? ? ?int?nodeIndex?=?head[0][0];
? ? ? ? ? ?visited[nodeIndex]?=?true;
? ? ? ? ? ?//跟堆頂元素相鄰的元素
? ? ? ? ? ?for?(int?j?=?0?;?j?<?nodes.length?;?j?++) {
? ? ? ? ? ? ? ?//找到相鄰節(jié)點(diǎn)
? ? ? ? ? ? ? ?if?(visited[j]?||?Integer.MAX_VALUE?==?adjacencyMatrix[nodeIndex][j]) {
? ? ? ? ? ? ? ? ? ?continue;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?for?(int?i?=?0?;?i?<?processNodes.heap.size() ;?i++) {
? ? ? ? ? ? ? ? ? ?int[][]?node?=?processNodes.heap.get(i);
? ? ? ? ? ? ? ? ? ?//找到節(jié)點(diǎn)并且值變小，需要調(diào)整
? ? ? ? ? ? ? ? ? ?if?(node[0][0]?==?j?&&?node[0][1]?>?head[0][1]?+?adjacencyMatrix[nodeIndex][j]) {
? ? ? ? ? ? ? ? ? ? ? ?processNodes.changeValue(i,?head[0][1]?+?adjacencyMatrix[nodeIndex][j]);
? ? ? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? }
? ? ? ? ? }

? ? ? }
? }

測試

public?static?void?main(String[]?args) {
? ? ? ?char[]?values?=?new?char[]{'A','B','C','D','E','F','G','H'};
? ? ? ?String[]?edges?=?new?String[]{"0,1,2","0,2,3","0,3,4","1,4,6","2,4,3","3,4,1","4,5,1","4,6,4","5,7,2","6,7,2"};
? ? ? ?Dijkstra?dijkstra?=?new?Dijkstra();
? ? ? ?dijkstra.initGraph(values,?edges);
? ? ? ?int?startNodeIndex?=?0;
? ? ? ?dijkstra.initDijkstra(startNodeIndex);
? ? ? ?dijkstra.dijkstra();
? ? ? ?for?(int[][]?node?:?dijkstra.finallyNodes) {
? ? ? ? ? ?System.out.println(dijkstra.nodes[node[0][0]].value?+?"距離"?+?dijkstra.nodes[startNodeIndex].value?+?"最短路徑為："?+?node[0][1]);
? ? ? }
? }