假期過(guò)長(zhǎng)，導(dǎo)致停更了好長(zhǎng)時(shí)間，復(fù)習(xí)一道算法題找找感覺(jué)。

前段時(shí)間看到一篇文章，里面提到了統(tǒng)治世界的十大算法，其中之一就是迪杰斯特拉算法(Dijkstra)，該算法主要解決的”最短路徑“這一類問(wèn)題。說(shuō)法雖然夸張了點(diǎn)，但它在實(shí)際生活中確實(shí)應(yīng)用廣泛，例如地圖軟件等，大部分游戲中自動(dòng)尋路等功能，使用到的 A*搜索算法也是基于迪杰斯特拉算法優(yōu)化而來(lái)。那么迪杰斯特拉算法是如何實(shí)現(xiàn)的呢？

假如我們現(xiàn)在有如下一個(gè)有向圖，圖中有 6 個(gè)頂點(diǎn)，編號(hào)分別為 1~6，帶有箭頭的直線表示的是能從一個(gè)頂點(diǎn)到達(dá)另外一個(gè)頂點(diǎn)，直線上的數(shù)字表示的是兩個(gè)頂點(diǎn)之間的距離，現(xiàn)在求頂點(diǎn) 1 到頂點(diǎn) 6 的最短距離。

由于圖中的點(diǎn)比較少，我們直接手動(dòng)計(jì)算就能算出來(lái)這個(gè)結(jié)果，但是如果頂點(diǎn)很多，有成千上萬(wàn)個(gè)，手動(dòng)計(jì)算就很難了，我們只能通過(guò)程序來(lái)計(jì)算，那么我們的程序該如何寫(xiě)呢？

思路

從圖中我們可以看到，頂點(diǎn) 1 只能直接到達(dá)頂點(diǎn) 2、3、5，不能直接到達(dá)頂點(diǎn) 6，所以要想從 1 到達(dá) 6，就必須得從其他頂點(diǎn)中轉(zhuǎn)。

我們定義一個(gè)數(shù)組，用來(lái)表示每個(gè)頂點(diǎn)到頂點(diǎn) 1 的距離，數(shù)組的索引表示的是頂點(diǎn)編號(hào)，數(shù)組元素的值表示的是到頂點(diǎn) 1 的最小距離。

開(kāi)始我們?cè)陧旤c(diǎn) 1 上，頂點(diǎn) 1 能到達(dá) 2、3、5，數(shù)組的狀態(tài)如下。

索引123456

最小距離	0	60	10	null	50	null

從頂點(diǎn) 2 處中轉(zhuǎn)，頂點(diǎn) 2 能到達(dá)頂點(diǎn) 4，距離為 35，所以頂點(diǎn) 1 到頂點(diǎn) 4 的距離為 60+35=95，數(shù)組狀態(tài)如下：

索引123456

最小距離	0	60	10	95	50	null

從頂點(diǎn) 3 處中轉(zhuǎn)，頂點(diǎn) 3 能到達(dá) 4，距離為 30。如果通過(guò)頂點(diǎn) 3 中轉(zhuǎn)，那么 1 到達(dá) 4 的距離為 40，小于經(jīng)過(guò) 2 中轉(zhuǎn)的距離，所以數(shù)組中到頂點(diǎn) 4 的距離更新為 40。頂點(diǎn) 3 還能到達(dá)頂點(diǎn) 5，同理，通過(guò)頂點(diǎn) 2 中轉(zhuǎn)，1 到達(dá) 5 的距離為 10+25=35，小于 1 直接到達(dá) 5 的距離，因此數(shù)組中到達(dá)頂點(diǎn) 5 的距離更新為 35，更新后，數(shù)組狀態(tài)如下：

索引123456

最小距離	0	60	10	40	35	null

從頂點(diǎn) 5 中轉(zhuǎn)，頂點(diǎn) 5 能到達(dá) 2，如果頂點(diǎn) 1 通過(guò)頂點(diǎn) 5 到達(dá) 2，距離為 35+30=65，大于頂點(diǎn) 1 直接到達(dá) 2，所以不更新。由于頂點(diǎn) 2 在前面已經(jīng)遍歷過(guò)它能到達(dá)哪些點(diǎn)了，所以后面不需要再遍歷它。頂點(diǎn) 5 還能到達(dá)頂點(diǎn) 6，所以此時(shí) 1 到達(dá) 6 的距離為 35+105=140，數(shù)組狀態(tài)如下：

索引123456

最小距離	0	60	10	40	35	140

從頂點(diǎn) 4 中轉(zhuǎn)，頂點(diǎn) 4 也能達(dá)到頂點(diǎn) 6。如果通過(guò)頂點(diǎn) 4 中轉(zhuǎn)，那么 1 到達(dá) 6 的距離為 40+15=55，這個(gè)距離小于從 5 中轉(zhuǎn)，所以更新數(shù)組，更新后，數(shù)組狀態(tài)如下：

索引123456

最小距離	0	60	10	40	35	55

以上流程，就是迪杰斯特拉算法在計(jì)算最短路徑問(wèn)題時(shí)的核心流程。

代碼實(shí)現(xiàn)

首先我們需要將這個(gè)有向圖用代碼表示出來(lái)，通常表示圖的方法有兩種：第一種是鄰接矩陣(也就是二維數(shù)組)，第二種是鄰接表(也就是數(shù)組+鏈表)，這里我們選用鄰接表法來(lái)表示一個(gè)有向圖。

另外我們還需要定義頂點(diǎn)之間的邊，一條邊有起點(diǎn)和終點(diǎn)，還有邊的權(quán)重信息，也就是長(zhǎng)度，用類 Edge 表示。代碼如下：

private?class?Edge?{
????//?起始定點(diǎn)
????public?int?s;
????//?終止定點(diǎn)
????public?int?t;
????//?邊的權(quán)重
????public?int?weight;

????Edge(int?s,?int?t,?int?weight)?{
????????this.s?=?s;
????????this.t?=?t;
????????this.weight?=?weight;
????}
}

有向圖我們用類 Graph 表示，類中有兩個(gè)屬性：頂點(diǎn)個(gè)數(shù) v 和描述頂點(diǎn)之間邊的信息的數(shù)組 adj，我們還提供了一個(gè)方法：addEdge，用來(lái)在兩個(gè)頂點(diǎn)之間添加一條邊。代碼如下：

public?class?Graph?{

????//?頂點(diǎn)個(gè)數(shù)(頂點(diǎn)編號(hào)從0開(kāi)始，在本文例子中，編號(hào)為0的頂點(diǎn)不存在)
????private?int?v;

????//?記錄每個(gè)頂點(diǎn)的邊
????private?LinkedList[]?adj;public?Graph(int?v)?{this.v?=?v;//?初始化this.adj?=?new?LinkedList[v];for?(int?i?=?0;?i?????????????adj[i]?=?new?LinkedList();
????????}
????}//?添加一條邊，從s到達(dá)tpublic?void?addEdge(int?s,?int?t,?int?weight)?{
????????Edge?edge?=?new?Edge(s,?t,?weight);
????????adj[s].add(edge);
????}
}

定義好了圖的描述信息后，接下來(lái)通過(guò)代碼來(lái)實(shí)現(xiàn)迪杰斯特拉算法，其代碼和注釋如下。

有兩處邏輯稍微解釋一下。第一處：flag 數(shù)組記錄的是已經(jīng)遍歷過(guò)的頂點(diǎn)，用來(lái)防止死循環(huán)，例如頂點(diǎn) 1 能到達(dá) 2，我們接著會(huì)判斷 2 能到達(dá)哪些點(diǎn)，頂點(diǎn) 1 又能到達(dá) 5，5 也能到達(dá) 2，如果沒(méi)有 flag 數(shù)組來(lái)記錄頂點(diǎn) 2 我們已經(jīng)遍歷過(guò)了，那么我們就會(huì)繼續(xù)遍歷 2，這樣會(huì)導(dǎo)致死循環(huán)。第二處：predecessor 數(shù)組記錄的是路徑信息，數(shù)組的索引表示的頂點(diǎn)編號(hào)，元素的值表示的是哪一個(gè)頂點(diǎn)到達(dá)當(dāng)前頂點(diǎn)的，例如：predecessor[3]=1 表示的是通過(guò)頂點(diǎn) 1 到達(dá)的頂點(diǎn) 3。

//?采用迪杰斯特拉算法找出從s到t的最短路徑
public?void?dijkstra(int?s,?int?t)?{
????int[]?dist?=?new?int[v];????//?記錄s到每個(gè)頂點(diǎn)的最小距離，數(shù)組下標(biāo)表示頂點(diǎn)編號(hào)，值表示最小距離
????boolean[]?flag?=?new?boolean[v];????//?記錄遍歷過(guò)的頂點(diǎn)，數(shù)組下標(biāo)表示頂點(diǎn)編號(hào)，值表示是否遍歷過(guò)該頂點(diǎn)
????for?(int?i?=?0;?i?????????dist[i]?=?Integer.MAX_VALUE;????//?初始狀態(tài)下，將頂點(diǎn)s到其他頂點(diǎn)的距離都設(shè)置為無(wú)窮大
????}
????int[]?predecessor?=?new?int[v];?????//?記錄路徑，索引表示頂點(diǎn)編號(hào)，值表示到達(dá)當(dāng)前頂點(diǎn)的頂點(diǎn)是哪一個(gè)
????Queue?queue?=?new?LinkedList<>();
????queue.add(s);
????dist[s]?=?0;????//?s->s的路徑為0while?(!queue.isEmpty())?{
????????Integer?vertex?=?queue.poll();if?(flag[vertex])?continue;?//?已經(jīng)遍歷過(guò)該頂點(diǎn)，就不再遍歷
????????flag[vertex]?=?true;for?(int?i?=?0;?i?????????????Edge?edge?=?adj[vertex].get(i);if?(dist[vertex]?//?如果出現(xiàn)了比當(dāng)前路徑小的方式，就更新為更小路徑
????????????????dist[edge.t]?=?dist[vertex]?+?edge.weight;
????????????????predecessor[edge.t]?=?vertex;
????????????}
????????????queue.add(edge.t);
????????}
????}//?打印路徑
????System.out.println("最短距離："?+?dist[t]);
????System.out.print(s);
????print(s,?t,?predecessor);
}

print 函數(shù)的作用是打印從頂點(diǎn) s 到達(dá)頂點(diǎn) t 的最短路徑中，需要經(jīng)過(guò)哪些點(diǎn)，具體代碼如下，就是一個(gè)遞歸調(diào)用，比較簡(jiǎn)單：

//?打印路徑
private?void?print(int?s,?int?t,?int[]?predecessor)?{
????if?(t?==?s)?{
????????return;
????}
????print(s,?predecessor[t],?predecessor);
????System.out.print("?->?"?+?t);
}

測(cè)試

根據(jù)文中的示例，構(gòu)建一個(gè)圖，進(jìn)行結(jié)果測(cè)試，代碼如下：

public?static?void?main(String[]?args)?{
????//?構(gòu)建圖
????Graph?graph?=?new?Graph(7);
????graph.addEdge(1,?2,?60);
????graph.addEdge(1,?3,?10);
????graph.addEdge(1,?5,?50);
????graph.addEdge(2,?4,?35);
????graph.addEdge(3,?4,?30);
????graph.addEdge(3,?5,?25);
????graph.addEdge(4,?6,?15);
????graph.addEdge(5,?2,?30);
????graph.addEdge(5,?6,?105);
????//?計(jì)算最短距離
????graph.dijkstra(1,?6);
}

測(cè)試結(jié)果：

總結(jié)

迪杰斯特拉算法的思想與廣度優(yōu)先搜索(BFS)的思路比較像，每次找到自己能到達(dá)的頂點(diǎn)，然后依次往外擴(kuò)散，直到遍歷完所有頂點(diǎn)。

總結(jié)

以上是生活随笔為你收集整理的dijkstra算法_最短路径问题——迪杰斯特拉算法(Dijkstra)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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