秒殺幾道運(yùn)用Dijkstra算法的題目

讀完本文，可以去力扣解決如下題目：

743. 網(wǎng)絡(luò)延遲時(shí)間（中等）

1514. 概率最大的路徑（中等）

1631. 最小體力消耗路徑（中等）

其實(shí)，很多算法的底層原理異常簡(jiǎn)單，無(wú)非就是一步一步延伸，變得看起來(lái)好像特別復(fù)雜，特別牛逼。

但如果你看過(guò)歷史文章，應(yīng)該可以對(duì)算法形成自己的理解，就會(huì)發(fā)現(xiàn)很多算法都是換湯不換藥，毫無(wú)新意，非?？菰铩?/p>

比如，我們說(shuō)二叉樹(shù)非常重要，你把這個(gè)結(jié)構(gòu)掌握了，就會(huì)發(fā)現(xiàn) 動(dòng)態(tài)規(guī)劃，分治算法，回溯（DFS）算法，BFS 算法框架，Union-Find 并查集算法，二叉堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 就是把二叉樹(shù)翻來(lái)覆去的運(yùn)用。

那么本文又要告訴你，Dijkstra 算法（一般音譯成迪杰斯特拉算法）無(wú)非就是一個(gè) BFS 算法的加強(qiáng)版，它們都是從二叉樹(shù)的層序遍歷衍生出來(lái)的。

這也是為什么我在 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的框架思維 中這么強(qiáng)調(diào)二叉樹(shù)的原因。

下面我們由淺入深，從二叉樹(shù)的層序遍歷聊到 Dijkstra 算法，給出 Dijkstra 算法的代碼框架，順手秒殺幾道運(yùn)用 Dijkstra 算法的題目。

圖的抽象

前文 圖論第一期：遍歷基礎(chǔ) 說(shuō)過(guò)「圖」這種數(shù)據(jù)結(jié)構(gòu)的基本實(shí)現(xiàn)，圖中的節(jié)點(diǎn)一般就抽象成一個(gè)數(shù)字（索引），圖的具體實(shí)現(xiàn)一般是「鄰接矩陣」或者「鄰接表」。

比如上圖這幅圖用鄰接表和鄰接矩陣的存儲(chǔ)方式如下：

前文 圖論第二期：拓?fù)渑判?告訴你，我們用鄰接表的場(chǎng)景更多，結(jié)合上圖，一幅圖可以用如下 Java 代碼表示：

// graph［s］ 存儲(chǔ)節(jié)點(diǎn) s 指向的節(jié)點(diǎn)（出度）

List《Integer》［］ graph;

如果你想把一個(gè)問(wèn)題抽象成「圖」的問(wèn)題，那么首先要實(shí)現(xiàn)一個(gè) APIadj：

// 輸入節(jié)點(diǎn) s 返回 s 的相鄰節(jié)點(diǎn)List《Integer》 adj（int s）;

類似多叉樹(shù)節(jié)點(diǎn)中的children字段記錄當(dāng)前節(jié)點(diǎn)的所有子節(jié)點(diǎn)，adj（s）就是計(jì)算一個(gè)節(jié)點(diǎn)s的相鄰節(jié)點(diǎn)。

比如上面說(shuō)的用鄰接表表示「圖」的方式，adj函數(shù)就可以這樣表示：

List《Integer》［］ graph;

// 輸入節(jié)點(diǎn) s，返回 s 的相鄰節(jié)點(diǎn)List《Integer》 adj（int s） {

return graph［s］;

}

當(dāng)然，對(duì)于「加權(quán)圖」，我們需要知道兩個(gè)節(jié)點(diǎn)之間的邊權(quán)重是多少，所以還可以抽象出一個(gè)weight方法：

// 返回節(jié)點(diǎn) from 到節(jié)點(diǎn) to 之間的邊的權(quán)重int weight（int from， int to）;

這個(gè)weight方法可以根據(jù)實(shí)際情況而定，因?yàn)椴煌乃惴}，題目給的「權(quán)重」含義可能不一樣，我們存儲(chǔ)權(quán)重的方式也不一樣。

有了上述基礎(chǔ)知識(shí)，就可以搞定 Dijkstra 算法了，下面我給你從二叉樹(shù)的層序遍歷開(kāi)始推演出 Dijkstra 算法的實(shí)現(xiàn)。

二叉樹(shù)層級(jí)遍歷和 BFS 算法

我們之前說(shuō)過(guò)二叉樹(shù)的層級(jí)遍歷框架：

// 輸入一棵二叉樹(shù)的根節(jié)點(diǎn)，層序遍歷這棵二叉樹(shù)void levelTraverse（TreeNode root） {

if （root == null） return 0;

Queue《TreeNode》 q = new LinkedList《》（）;

q.offer（root）;

int depth = 1;

// 從上到下遍歷二叉樹(shù)的每一層

while （！q.isEmpty（）） {

int sz = q.size（）;

// 從左到右遍歷每一層的每個(gè)節(jié)點(diǎn)

for （int i = 0; i 《 sz; i++） {

TreeNode cur = q.poll（）;

printf（“節(jié)點(diǎn) %s 在第 %s 層”， cur， depth）;

// 將下一層節(jié)點(diǎn)放入隊(duì)列

if （cur.left ！= null） {

q.offer（cur.left）;

}

if （cur.right ！= null） {

q.offer（cur.right）;

}

}

depth++;

}

}

我們先來(lái)思考一個(gè)問(wèn)題，注意二叉樹(shù)的層級(jí)遍歷while循環(huán)里面還套了個(gè)for循環(huán)，為什么要這樣？

while循環(huán)和for循環(huán)的配合正是這個(gè)遍歷框架設(shè)計(jì)的巧妙之處

while循環(huán)控制一層一層往下走，for循環(huán)利用sz變量控制從左到右遍歷每一層二叉樹(shù)節(jié)點(diǎn)。

注意我們代碼框架中的depth變量，其實(shí)就記錄了當(dāng)前遍歷到的層數(shù)。換句話說(shuō)，每當(dāng)我們遍歷到一個(gè)節(jié)點(diǎn)cur，都知道這個(gè)節(jié)點(diǎn)屬于第幾層。

算法題經(jīng)常會(huì)問(wèn)二叉樹(shù)的最大深度呀，最小深度呀，層序遍歷結(jié)果呀，等等問(wèn)題，所以記錄下來(lái)這個(gè)深度depth是有必要的。

基于二叉樹(shù)的遍歷框架，我們又可以擴(kuò)展出多叉樹(shù)的層序遍歷框架：

// 輸入一棵多叉樹(shù)的根節(jié)點(diǎn)，層序遍歷這棵多叉樹(shù)void levelTraverse（TreeNode root） {

if （root == null） return 0;

Queue《TreeNode》 q = new LinkedList《》（）;

q.offer（root）;

int depth = 1;

// 從上到下遍歷多叉樹(shù)的每一層

while （！q.isEmpty（）） {

int sz = q.size（）;

// 從左到右遍歷每一層的每個(gè)節(jié)點(diǎn)

for （int i = 0; i 《 sz; i++） {

TreeNode cur = q.poll（）;

printf（“節(jié)點(diǎn) %s 在第 %s 層”， cur， depth）;

// 將下一層節(jié)點(diǎn)放入隊(duì)列

for （TreeNode child ： root.children） {

q.offer（child）;

}

}

depth++;

}

}

基于多叉樹(shù)的遍歷框架，我們又可以擴(kuò)展出 BFS（廣度優(yōu)先搜索）的算法框架：

// 輸入起點(diǎn)，進(jìn)行 BFS 搜索int BFS（Node start） {

Queue《Node》 q; // 核心數(shù)據(jù)結(jié)構(gòu)

Set《Node》 visited; // 避免走回頭路

q.offer（start）; // 將起點(diǎn)加入隊(duì)列

visited.add（start）;

int step = 0; // 記錄搜索的步數(shù)

while （q not empty） {

int sz = q.size（）;

/* 將當(dāng)前隊(duì)列中的所有節(jié)點(diǎn)向四周擴(kuò)散一步 */

for （int i = 0; i 《 sz; i++） {

Node cur = q.poll（）;

printf（“從 %s 到 %s 的最短距離是 %s”， start， cur， step）;

/* 將 cur 的相鄰節(jié)點(diǎn)加入隊(duì)列 */

for （Node x ： cur.adj（）） {

if （x not in visited） {

q.offer（x）;

visited.add（x）;

}

}

}

step++;

}

}

如果對(duì) BFS 算法不熟悉，可以看前文 BFS 算法框架，這里只是為了讓你做個(gè)對(duì)比，所謂 BFS 算法，就是把算法問(wèn)題抽象成一幅「無(wú)權(quán)圖」，然后繼續(xù)玩二叉樹(shù)層級(jí)遍歷那一套罷了。

注意，我們的 BFS 算法框架也是while循環(huán)嵌套for循環(huán)的形式，也用了一個(gè)step變量記錄for循環(huán)執(zhí)行的次數(shù)，無(wú)非就是多用了一個(gè)visited集合記錄走過(guò)的節(jié)點(diǎn)，防止走回頭路罷了。

為什么這樣呢？

所謂「無(wú)權(quán)圖」，與其說(shuō)每條「邊」沒(méi)有權(quán)重，不如說(shuō)每條「邊」的權(quán)重都是 1，從起點(diǎn)start到任意一個(gè)節(jié)點(diǎn)之間的路徑權(quán)重就是它們之間「邊」的條數(shù)，那可不就是step變量記錄的值么？

再加上 BFS 算法利用for循環(huán)一層一層向外擴(kuò)散的邏輯和visited集合防止走回頭路的邏輯，當(dāng)你每次從隊(duì)列中拿出節(jié)點(diǎn)cur的時(shí)候，從start到cur的最短權(quán)重就是step記錄的步數(shù)。

但是，到了「加權(quán)圖」的場(chǎng)景，事情就沒(méi)有這么簡(jiǎn)單了，因?yàn)槟悴荒苣J(rèn)每條邊的「權(quán)重」都是 1 了，這個(gè)權(quán)重可以是任意正數(shù)（Dijkstra 算法要求不能存在負(fù)權(quán)重邊），比如下圖的例子：

如果沿用 BFS 算法中的step變量記錄「步數(shù)」，顯然紅色路徑一步就可以走到終點(diǎn)，但是這一步的權(quán)重很大；正確的最小權(quán)重路徑應(yīng)該是綠色的路徑，雖然需要走很多步，但是路徑權(quán)重依然很小。

其實(shí) Dijkstra 和 BFS 算法差不多，不過(guò)在講解 Dijkstra 算法框架之前，我們首先需要對(duì)之前的框架進(jìn)行如下改造：

想辦法去掉while循環(huán)里面的for循環(huán)。

為什么？有了剛才的鋪墊，這個(gè)不難理解，剛才說(shuō)for循環(huán)是干什么用的來(lái)著？

是為了讓二叉樹(shù)一層一層往下遍歷，讓 BFS 算法一步一步向外擴(kuò)散，因?yàn)檫@個(gè)層數(shù)depth，或者這個(gè)步數(shù)step，在之前的場(chǎng)景中有用。

但現(xiàn)在我們想解決「加權(quán)圖」中的最短路徑問(wèn)題，「步數(shù)」已經(jīng)沒(méi)有參考意義了，「路徑的權(quán)重之和」才有意義，所以這個(gè)for循環(huán)可以被去掉。

怎么去掉？就拿二叉樹(shù)的層級(jí)遍歷來(lái)說(shuō)，其實(shí)你可以直接去掉for循環(huán)相關(guān)的代碼：

// 輸入一棵二叉樹(shù)的根節(jié)點(diǎn)，遍歷這棵二叉樹(shù)所有節(jié)點(diǎn)void levelTraverse（TreeNode root） {

if （root == null） return 0;

Queue《TreeNode》 q = new LinkedList《》（）;

q.offer（root）;

// 遍歷二叉樹(shù)的每一個(gè)節(jié)點(diǎn)

while （！q.isEmpty（）） {

TreeNode cur = q.poll（）;

printf（“我不知道節(jié)點(diǎn) %s 在第幾層”， cur）;

// 將子節(jié)點(diǎn)放入隊(duì)列

if （cur.left ！= null） {

q.offer（cur.left）;

}

if （cur.right ！= null） {

q.offer（cur.right）;

}

}

}

但問(wèn)題是，沒(méi)有for循環(huán)，你也沒(méi)辦法維護(hù)depth變量了。

如果你想同時(shí)維護(hù)depth變量，讓每個(gè)節(jié)點(diǎn)cur知道自己在第幾層，可以想其他辦法，比如新建一個(gè)State類，記錄每個(gè)節(jié)點(diǎn)所在的層數(shù)：

class State {

// 記錄 node 節(jié)點(diǎn)的深度

int depth;

TreeNode node;

State（TreeNode node， int depth） {

this.depth = depth;

this.node = node;

}

}

// 輸入一棵二叉樹(shù)的根節(jié)點(diǎn)，遍歷這棵二叉樹(shù)所有節(jié)點(diǎn)void levelTraverse（TreeNode root） {

if （root == null） return 0;

Queue《State》 q = new LinkedList《》（）;

q.offer（new State（root， 1））;

// 遍歷二叉樹(shù)的每一個(gè)節(jié)點(diǎn)

while （！q.isEmpty（）） {

State cur = q.poll（）;

TreeNode cur_node = cur.node;

int cur_depth = cur.depth;

printf（“節(jié)點(diǎn) %s 在第 %s 層”， cur_node， cur_depth）;

// 將子節(jié)點(diǎn)放入隊(duì)列

if （cur_node.left ！= null） {

q.offer（new State（cur_node.left， cur_depth + 1））;

}

if （cur_node.right ！= null） {

q.offer（new State（cur_node.right， cur_depth + 1））;

}

}

}

這樣，我們就可以不使用for循環(huán)也確切地知道每個(gè)二叉樹(shù)節(jié)點(diǎn)的深度了。

如果你能夠理解上面這段代碼，我們就可以來(lái)看 Dijkstra 算法的代碼框架了。

Dijkstra 算法框架

首先，我們先看一下 Dijkstra 算法的簽名：

// 輸入一幅圖和一個(gè)起點(diǎn) start，計(jì)算 start 到其他節(jié)點(diǎn)的最短距離int［］ dijkstra（int start， List《Integer》［］ graph）;

輸入是一幅圖graph和一個(gè)起點(diǎn)start，返回是一個(gè)記錄最短路徑權(quán)重的數(shù)組。

比方說(shuō)，輸入起點(diǎn)start = 3，函數(shù)返回一個(gè)int［］數(shù)組，假設(shè)賦值給distTo變量，那么從起點(diǎn)3到節(jié)點(diǎn)6的最短路徑權(quán)重的值就是distTo［6］。

是的，標(biāo)準(zhǔn)的 Dijkstra 算法會(huì)把從起點(diǎn)start到所有其他節(jié)點(diǎn)的最短路徑都算出來(lái)。

當(dāng)然，如果你的需求只是計(jì)算從起點(diǎn)start到某一個(gè)終點(diǎn)end的最短路徑，那么在標(biāo)準(zhǔn) Dijkstra 算法上稍作修改就可以更高效地完成這個(gè)需求，這個(gè)我們后面再說(shuō)。

其次，我們也需要一個(gè)State類來(lái)輔助算法的運(yùn)行：

class State {

// 圖節(jié)點(diǎn)的 id

int id;

// 從 start 節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的距離

int distFromStart;

State（int id， int distFromStart） {

this.id = id;

this.distFromStart = distFromStart;

}

}

類似剛才二叉樹(shù)的層序遍歷，我們也需要用State類記錄一些額外信息，也就是使用distFromStart變量記錄從起點(diǎn)start到當(dāng)前這個(gè)節(jié)點(diǎn)的距離。

剛才說(shuō)普通 BFS 算法中，根據(jù) BFS 的邏輯和無(wú)權(quán)圖的特點(diǎn)，第一次遇到某個(gè)節(jié)點(diǎn)所走的步數(shù)就是最短距離，所以用一個(gè)visited數(shù)組防止走回頭路，每個(gè)節(jié)點(diǎn)只會(huì)經(jīng)過(guò)一次。

加權(quán)圖中的 Dijkstra 算法和無(wú)權(quán)圖中的普通 BFS 算法不同，在 Dijkstra 算法中，你第一次經(jīng)過(guò)某個(gè)節(jié)點(diǎn)時(shí)的路徑權(quán)重，不見(jiàn)得就是最小的，所以對(duì)于同一個(gè)節(jié)點(diǎn)，我們可能會(huì)經(jīng)過(guò)多次，而且每次的distFromStart可能都不一樣，比如下圖：

我會(huì)經(jīng)過(guò)節(jié)點(diǎn)5三次，每次的distFromStart值都不一樣，那我取distFromStart最小的那次，不就是從起點(diǎn)start到節(jié)點(diǎn)5的最短路徑權(quán)重了么？

好了，明白上面的幾點(diǎn)，我們可以來(lái)看看 Dijkstra 算法的代碼模板。

其實(shí)，Dijkstra 可以理解成一個(gè)帶 dp table（或者說(shuō)備忘錄）的 BFS 算法，偽碼如下：

// 返回節(jié)點(diǎn) from 到節(jié)點(diǎn) to 之間的邊的權(quán)重int weight（int from， int to）;

// 輸入節(jié)點(diǎn) s 返回 s 的相鄰節(jié)點(diǎn)List《Integer》 adj（int s）;

// 輸入一幅圖和一個(gè)起點(diǎn) start，計(jì)算 start 到其他節(jié)點(diǎn)的最短距離int［］ dijkstra（int start， List《Integer》［］ graph） {

// 圖中節(jié)點(diǎn)的個(gè)數(shù)

int V = graph.length;

// 記錄最短路徑的權(quán)重，你可以理解為 dp table

// 定義：distTo［i］ 的值就是節(jié)點(diǎn) start 到達(dá)節(jié)點(diǎn) i 的最短路徑權(quán)重

int［］ distTo = new int［V］;

// 求最小值，所以 dp table 初始化為正無(wú)窮

Arrays.fill（distTo， Integer.MAX_VALUE）;

// base case，start 到 start 的最短距離就是 0

distTo［start］ = 0;

// 優(yōu)先級(jí)隊(duì)列，distFromStart 較小的排在前面

Queue《State》 pq = new PriorityQueue《》（（a， b） -》 {

return a.distFromStart - b.distFromStart;

}）;

// 從起點(diǎn) start 開(kāi)始進(jìn)行 BFS

pq.offer（new State（start， 0））;

while （！pq.isEmpty（）） {

State curState = pq.poll（）;

int curNodeID = curState.id;

int curDistFromStart = curState.distFromStart;

if （curDistFromStart 》 distTo［curNodeID］） {

// 已經(jīng)有一條更短的路徑到達(dá) curNode 節(jié)點(diǎn)了

continue;

}

// 將 curNode 的相鄰節(jié)點(diǎn)裝入隊(duì)列

for （int nextNodeID ： adj（curNodeID）） {

// 看看從 curNode 達(dá)到 nextNode 的距離是否會(huì)更短

int distToNextNode = distTo［curNodeID］ + weight（curNodeID， nextNodeID）;

if （distTo［nextNodeID］ 》 distToNextNode） {

// 更新 dp table

distTo［nextNodeID］ = distToNextNode;

// 將這個(gè)節(jié)點(diǎn)以及距離放入隊(duì)列

pq.offer（new State（nextNodeID， distToNextNode））;

}

}

}

return distTo;

}

對(duì)比普通的 BFS 算法，你可能會(huì)有以下疑問(wèn)：

1、沒(méi)有visited集合記錄已訪問(wèn)的節(jié)點(diǎn)，所以一個(gè)節(jié)點(diǎn)會(huì)被訪問(wèn)多次，會(huì)被多次加入隊(duì)列，那會(huì)不會(huì)導(dǎo)致隊(duì)列永遠(yuǎn)不為空，造成死循環(huán)？

2、為什么用優(yōu)先級(jí)隊(duì)列PriorityQueue而不是LinkedList實(shí)現(xiàn)的普通隊(duì)列？為什么要按照distFromStart的值來(lái)排序？

3、如果我只想計(jì)算起點(diǎn)start到某一個(gè)終點(diǎn)end的最短路徑，是否可以修改算法，提升一些效率？

我們先回答第一個(gè)問(wèn)題，為什么這個(gè)算法不用visited集合也不會(huì)死循環(huán)。

對(duì)于這類問(wèn)題，我教你一個(gè)思考方法：

循環(huán)結(jié)束的條件是隊(duì)列為空，那么你就要注意看什么時(shí)候往隊(duì)列里放元素（調(diào)用offer）方法，再注意看什么時(shí)候從隊(duì)列往外拿元素（調(diào)用poll方法）。

while循環(huán)每執(zhí)行一次，都會(huì)往外拿一個(gè)元素，但想往隊(duì)列里放元素，可就有很多限制了，必須滿足下面這個(gè)條件：

// 看看從 curNode 達(dá)到 nextNode 的距離是否會(huì)更短if （distTo［nextNodeID］ 》 distToNextNode） {

// 更新 dp table

distTo［nextNodeID］ = distToNextNode;

pq.offer（new State（nextNodeID， distToNextNode））;

}

這也是為什么我說(shuō)distTo數(shù)組可以理解成我們熟悉的 dp table，因?yàn)檫@個(gè)算法邏輯就是在不斷的最小化distTo數(shù)組中的元素：

如果你能讓到達(dá)nextNodeID的距離更短，那就更新distTo［nextNodeID］的值，讓你入隊(duì)，否則的話對(duì)不起，不讓入隊(duì)。

因?yàn)閮蓚€(gè)節(jié)點(diǎn)之間的最短距離（路徑權(quán)重）肯定是一個(gè)確定的值，不可能無(wú)限減小下去，所以隊(duì)列一定會(huì)空，隊(duì)列空了之后，distTo數(shù)組中記錄的就是從start到其他節(jié)點(diǎn)的最短距離。

接下來(lái)解答第二個(gè)問(wèn)題，為什么要用PriorityQueue而不是LinkedList實(shí)現(xiàn)的普通隊(duì)列？

如果你非要用普通隊(duì)列，其實(shí)也沒(méi)問(wèn)題的，你可以直接把PriorityQueue改成LinkedList，也能得到正確答案，但是效率會(huì)低很多。

Dijkstra 算法使用優(yōu)先級(jí)隊(duì)列，主要是為了效率上的優(yōu)化，類似一種貪心算法的思路。

為什么說(shuō)是一種貪心思路呢，比如說(shuō)下面這種情況，你想計(jì)算從起點(diǎn)start到終點(diǎn)end的最短路徑權(quán)重：

你下一步想遍歷那個(gè)節(jié)點(diǎn)？就當(dāng)前的情況來(lái)看，你覺(jué)得哪條路徑更有「潛力」成為最短路徑中的一部分？

從目前的情況來(lái)看，顯然橙色路徑的可能性更大嘛，所以我們希望節(jié)點(diǎn)2排在隊(duì)列靠前的位置，優(yōu)先被拿出來(lái)向后遍歷。

所以我們使用PriorityQueue作為隊(duì)列，讓distFromStart的值較小的節(jié)點(diǎn)排在前面，這就類似我們之前講 貪心算法 說(shuō)到的貪心思路，可以很大程度上優(yōu)化算法的效率。

大家應(yīng)該聽(tīng)過(guò) Bellman-Ford 算法，這個(gè)算法是一種更通用的最短路徑算法，因?yàn)樗梢蕴幚韼в胸?fù)權(quán)重邊的圖，Bellman-Ford 算法邏輯和 Dijkstra 算法非常類似，用到的就是普通隊(duì)列，本文就提一句，后面有空再具體寫。

接下來(lái)說(shuō)第三個(gè)問(wèn)題，如果只關(guān)心起點(diǎn)start到某一個(gè)終點(diǎn)end的最短路徑，是否可以修改代碼提升算法效率。

肯定可以的，因?yàn)槲覀儤?biāo)準(zhǔn) Dijkstra 算法會(huì)算出start到所有其他節(jié)點(diǎn)的最短路徑，你只想計(jì)算到end的最短路徑，相當(dāng)于減少計(jì)算量，當(dāng)然可以提升效率。

需要在代碼中做的修改也非常少，只要改改函數(shù)簽名，再加個(gè) if 判斷就行了：

// 輸入起點(diǎn) start 和終點(diǎn) end，計(jì)算起點(diǎn)到終點(diǎn)的最短距離int dijkstra（int start， int end， List《Integer》［］ graph） {

// 。..

while （！pq.isEmpty（）） {

State curState = pq.poll（）;

int curNodeID = curState.id;

int curDistFromStart = curState.distFromStart;

// 在這里加一個(gè)判斷就行了，其他代碼不用改

if （curNodeID == end） {

return curDistFromStart;

}

if （curDistFromStart 》 distTo［curNodeID］） {

continue;

}

// 。..

}

// 如果運(yùn)行到這里，說(shuō)明從 start 無(wú)法走到 end

return Integer.MAX_VALUE;

}

因?yàn)閮?yōu)先級(jí)隊(duì)列自動(dòng)排序的性質(zhì)，每次從隊(duì)列里面拿出來(lái)的都是distFromStart值最小的，所以當(dāng)你從隊(duì)頭拿出一個(gè)節(jié)點(diǎn)，如果發(fā)現(xiàn)這個(gè)節(jié)點(diǎn)就是終點(diǎn)end，那么distFromStart對(duì)應(yīng)的值就是從start到end的最短距離。

這個(gè)算法較之前的實(shí)現(xiàn)提前 return 了，所以效率有一定的提高。

時(shí)間復(fù)雜度分析

Dijkstra 算法的時(shí)間復(fù)雜度是多少？你去網(wǎng)上查，可能會(huì)告訴你是O（ElogV），其中E代表圖中邊的條數(shù)，V代表圖中節(jié)點(diǎn)的個(gè)數(shù)。

因?yàn)槔硐肭闆r下優(yōu)先級(jí)隊(duì)列中最多裝V個(gè)節(jié)點(diǎn)，對(duì)優(yōu)先級(jí)隊(duì)列的操作次數(shù)和E成正比，所以整體的時(shí)間復(fù)雜度就是O（ElogV）。

不過(guò)這是理想情況，Dijkstra 算法的代碼實(shí)現(xiàn)有很多版本，不同編程語(yǔ)言或者不同數(shù)據(jù)結(jié)構(gòu) API 都會(huì)導(dǎo)致算法的時(shí)間復(fù)雜度發(fā)生一些改變。

比如本文實(shí)現(xiàn)的 Dijkstra 算法，使用了 Java 的PriorityQueue這個(gè)數(shù)據(jù)結(jié)構(gòu)，這個(gè)容器類底層使用二叉堆實(shí)現(xiàn)，但沒(méi)有提供通過(guò)索引操作隊(duì)列中元素的 API，所以隊(duì)列中會(huì)有重復(fù)的節(jié)點(diǎn)，最多可能有E個(gè)節(jié)點(diǎn)存在隊(duì)列中。

所以本文實(shí)現(xiàn)的 Dijkstra 算法復(fù)雜度并不是理想情況下的O（ElogV），而是O（ElogE），可能會(huì)略大一些，因?yàn)閳D中邊的條數(shù)一般是大于節(jié)點(diǎn)的個(gè)數(shù)的。

不過(guò)就對(duì)數(shù)函數(shù)來(lái)說(shuō)，就算真數(shù)大一些，對(duì)數(shù)函數(shù)的結(jié)果也大不了多少，所以這個(gè)算法實(shí)現(xiàn)的實(shí)際運(yùn)行效率也是很高的，以上只是理論層面的時(shí)間復(fù)雜度分析，供大家參考。

秒殺三道題目

以上說(shuō)了 Dijkstra 算法的框架，下面我們套用這個(gè)框架做幾道題，實(shí)踐出真知。

第一題是力扣第 743 題「網(wǎng)絡(luò)延遲時(shí)間」，題目如下：

函數(shù)簽名如下：

// times 記錄邊和權(quán)重，n 為節(jié)點(diǎn)個(gè)數(shù)（從 1 開(kāi)始），k 為起點(diǎn)// 計(jì)算從 k 發(fā)出的信號(hào)至少需要多久傳遍整幅圖int networkDelayTime（int［］［］ times， int n， int k）

讓你求所有節(jié)點(diǎn)都收到信號(hào)的時(shí)間，你把所謂的傳遞時(shí)間看做距離，實(shí)際上就是問(wèn)你「從節(jié)點(diǎn)k到其他所有節(jié)點(diǎn)的最短路徑中，最長(zhǎng)的那條最短路徑距離是多少」，說(shuō)白了就是讓你算從節(jié)點(diǎn)k出發(fā)到其他所有節(jié)點(diǎn)的最短路徑，就是標(biāo)準(zhǔn)的 Dijkstra 算法。

在用 Dijkstra 之前，別忘了要滿足一些條件，加權(quán)有向圖，沒(méi)有負(fù)權(quán)重邊，OK，可以用 Dijkstra 算法計(jì)算最短路徑。

根據(jù)我們之前 Dijkstra 算法的框架，我們可以寫出下面代碼：

public int networkDelayTime（int［］［］ times， int n， int k） {

// 節(jié)點(diǎn)編號(hào)是從 1 開(kāi)始的，所以要一個(gè)大小為 n + 1 的鄰接表

List《int［］》［］ graph = new LinkedList［n + 1］;

for （int i = 1; i 《= n; i++） {

graph［i］ = new LinkedList《》（）;

}

// 構(gòu)造圖

for （int［］ edge ： times） {

int from = edge［0］;

int to = edge［1］;

int weight = edge［2］;

// from -》 List《（to， weight）》

// 鄰接表存儲(chǔ)圖結(jié)構(gòu)，同時(shí)存儲(chǔ)權(quán)重信息

graph［from］.add（new int［］{to， weight}）;

}

// 啟動(dòng) dijkstra 算法計(jì)算以節(jié)點(diǎn) k 為起點(diǎn)到其他節(jié)點(diǎn)的最短路徑

int［］ distTo = dijkstra（k， graph）;

// 找到最長(zhǎng)的那一條最短路徑

int res = 0;

for （int i = 1; i 《 distTo.length; i++） {

if （distTo［i］ == Integer.MAX_VALUE） {

// 有節(jié)點(diǎn)不可達(dá)，返回 -1

return -1;

}

res = Math.max（res， distTo［i］）;

}

return res;

}

// 輸入一個(gè)起點(diǎn) start，計(jì)算從 start 到其他節(jié)點(diǎn)的最短距離int［］ dijkstra（int start， List《int［］》［］ graph） {}

上述代碼首先利用題目輸入的數(shù)據(jù)轉(zhuǎn)化成鄰接表表示一幅圖，接下來(lái)我們可以直接套用 Dijkstra 算法的框架：

class State {

// 圖節(jié)點(diǎn)的 id

int id;

// 從 start 節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的距離

int distFromStart;

State（int id， int distFromStart） {

this.id = id;

this.distFromStart = distFromStart;

}

}

// 輸入一個(gè)起點(diǎn) start，計(jì)算從 start 到其他節(jié)點(diǎn)的最短距離int［］ dijkstra（int start， List《int［］》［］ graph） {

// 定義：distTo［i］ 的值就是起點(diǎn) start 到達(dá)節(jié)點(diǎn) i 的最短路徑權(quán)重

int［］ distTo = new int［graph.length］;

Arrays.fill（distTo， Integer.MAX_VALUE）;

// base case，start 到 start 的最短距離就是 0

distTo［start］ = 0;

// 優(yōu)先級(jí)隊(duì)列，distFromStart 較小的排在前面

Queue《State》 pq = new PriorityQueue《》（（a， b） -》 {

return a.distFromStart - b.distFromStart;

}）;

// 從起點(diǎn) start 開(kāi)始進(jìn)行 BFS

pq.offer（new State（start， 0））;

while （！pq.isEmpty（）） {

State curState = pq.poll（）;

int curNodeID = curState.id;

int curDistFromStart = curState.distFromStart;

if （curDistFromStart 》 distTo［curNodeID］） {

continue;

}

// 將 curNode 的相鄰節(jié)點(diǎn)裝入隊(duì)列

for （int［］ neighbor ： graph［curNodeID］） {

int nextNodeID = neighbor［0］;

int distToNextNode = distTo［curNodeID］ + neighbor［1］;

// 更新 dp table

if （distTo［nextNodeID］ 》 distToNextNode） {

distTo［nextNodeID］ = distToNextNode;

pq.offer（new State（nextNodeID， distToNextNode））;

}

}

}

return distTo;

}

你對(duì)比之前說(shuō)的代碼框架，只要稍稍修改，就可以把這道題目解決了。

感覺(jué)這道題完全沒(méi)有難度，下面我們?cè)倏匆坏李}目，力扣第 1631 題「最小體力消耗路徑」：

函數(shù)簽名如下：

// 輸入一個(gè)二維矩陣，計(jì)算從左上角到右下角的最小體力消耗int minimumEffortPath（int［］［］ heights）;

我們常見(jiàn)的二維矩陣題目，如果讓你從左上角走到右下角，比較簡(jiǎn)單的題一般都會(huì)限制你只能向右或向下走，但這道題可沒(méi)有限制哦，你可以上下左右隨便走，只要路徑的「體力消耗」最小就行。

如果你把二維數(shù)組中每個(gè)（x， y）坐標(biāo)看做一個(gè)節(jié)點(diǎn)，它的上下左右坐標(biāo)就是相鄰節(jié)點(diǎn)，它對(duì)應(yīng)的值和相鄰坐標(biāo)對(duì)應(yīng)的值之差的絕對(duì)值就是題目說(shuō)的「體力消耗」，你就可以理解為邊的權(quán)重。

這樣一想，是不是就在讓你以左上角坐標(biāo)為起點(diǎn)，以右下角坐標(biāo)為終點(diǎn)，計(jì)算起點(diǎn)到終點(diǎn)的最短路徑？Dijkstra 算法是不是可以做到？

// 輸入起點(diǎn) start 和終點(diǎn) end，計(jì)算起點(diǎn)到終點(diǎn)的最短距離int dijkstra（int start， int end， List《Integer》［］ graph）

只不過(guò)，這道題中評(píng)判一條路徑是長(zhǎng)還是短的標(biāo)準(zhǔn)不再是路徑經(jīng)過(guò)的權(quán)重總和，而是路徑經(jīng)過(guò)的權(quán)重最大值。

明白這一點(diǎn)，再想一下使用 Dijkstra 算法的前提，加權(quán)有向圖，沒(méi)有負(fù)權(quán)重邊，求最短路徑，OK，可以使用，咱們來(lái)套框架。

二維矩陣抽象成圖，我們先實(shí)現(xiàn)一下圖的adj方法，之后的主要邏輯會(huì)清晰一些：

// 方向數(shù)組，上下左右的坐標(biāo)偏移量int［］［］ dirs = new int［］［］{{0，1}， {1，0}， {0，-1}， {-1，0}};

// 返回坐標(biāo) （x， y） 的上下左右相鄰坐標(biāo)

List《int［］》 adj（int［］［］ matrix， int x， int y） {

int m = matrix.length， n = matrix［0］.length;

// 存儲(chǔ)相鄰節(jié)點(diǎn)

List《int［］》 neighbors = new ArrayList《》（）;

for （int［］ dir ： dirs） {

int nx = x + dir［0］;

int ny = y + dir［1］;

if （nx 》= m || nx 《 0 || ny 》= n || ny 《 0） {

// 索引越界

continue;

}

neighbors.add（new int［］{nx， ny}）;

}

return neighbors;

}

類似的，我們現(xiàn)在認(rèn)為一個(gè)二維坐標(biāo)（x， y）是圖中的一個(gè)節(jié)點(diǎn)，所以這個(gè)State類也需要修改一下：

class State {

// 矩陣中的一個(gè)位置

int x， y;

// 從起點(diǎn) （0， 0） 到當(dāng)前位置的最小體力消耗（距離）

int effortFromStart;

State（int x， int y， int effortFromStart） {

this.x = x;

this.y = y;

this.effortFromStart = effortFromStart;

}

}

接下來(lái)，就可以套用 Dijkstra 算法的代碼模板了：

// Dijkstra 算法，計(jì)算 （0， 0） 到 （m - 1， n - 1） 的最小體力消耗int minimumEffortPath（int［］［］ heights） {

int m = heights.length， n = heights［0］.length;

// 定義：從 （0， 0） 到 （i， j） 的最小體力消耗是 effortTo［i］［j］

int［］［］ effortTo = new int［m］［n］;

// dp table 初始化為正無(wú)窮

for （int i = 0; i 《 m; i++） {

Arrays.fill（effortTo［i］， Integer.MAX_VALUE）;

}

// base case，起點(diǎn)到起點(diǎn)的最小消耗就是 0

effortTo［0］［0］ = 0;

// 優(yōu)先級(jí)隊(duì)列，effortFromStart 較小的排在前面

Queue《State》 pq = new PriorityQueue《》（（a， b） -》 {

return a.effortFromStart - b.effortFromStart;

}）;

// 從起點(diǎn) （0， 0） 開(kāi)始進(jìn)行 BFS

pq.offer（new State（0， 0， 0））;

while （！pq.isEmpty（）） {

State curState = pq.poll（）;

int curX = curState.x;

int curY = curState.y;

int curEffortFromStart = curState.effortFromStart;

// 到達(dá)終點(diǎn)提前結(jié)束

if （curX == m - 1 && curY == n - 1） {

return curEffortFromStart;

}

if （curEffortFromStart 》 effortTo［curX］［curY］） {

continue;

}

// 將 （curX， curY） 的相鄰坐標(biāo)裝入隊(duì)列

for （int［］ neighbor ： adj（heights， curX， curY）） {

int nextX = neighbor［0］;

int nextY = neighbor［1］;

// 計(jì)算從 （curX， curY） 達(dá)到 （nextX， nextY） 的消耗

int effortToNextNode = Math.max（

effortTo［curX］［curY］，

Math.abs（heights［curX］［curY］ - heights［nextX］［nextY］）

）;

// 更新 dp table

if （effortTo［nextX］［nextY］ 》 effortToNextNode） {

effortTo［nextX］［nextY］ = effortToNextNode;

pq.offer（new State（nextX， nextY， effortToNextNode））;

}

}

}

// 正常情況不會(huì)達(dá)到這個(gè) return

return -1;

}

你看，稍微改一改代碼模板，這道題就解決了。

最后看一道題吧，力扣第 1514 題「概率最大的路徑」，看下題目：

函數(shù)簽名如下：

// 輸入一幅無(wú)向圖，邊上的權(quán)重代表概率，返回從 start 到達(dá) end 最大的概率double maxProbability（int n， int［］［］ edges， double［］ succProb， int start， int end）

我說(shuō)這題一看就是 Dijkstra 算法，但聰明的你肯定會(huì)反駁我：

1、這題給的是無(wú)向圖，也可以用 Dijkstra 算法嗎？

2、更重要的是，Dijkstra 算法計(jì)算的是最短路徑，計(jì)算的是最小值，這題讓你計(jì)算最大概率是一個(gè)最大值，怎么可能用 Dijkstra 算法呢？

問(wèn)得好！

首先關(guān)于有向圖和無(wú)向圖，前文 圖算法基礎(chǔ) 說(shuō)過(guò)，無(wú)向圖本質(zhì)上可以認(rèn)為是「雙向圖」，從而轉(zhuǎn)化成有向圖。

重點(diǎn)說(shuō)說(shuō)最大值和最小值這個(gè)問(wèn)題，其實(shí) Dijkstra 和很多最優(yōu)化算法一樣，計(jì)算的是「最優(yōu)值」，這個(gè)最優(yōu)值可能是最大值，也可能是最小值。

標(biāo)準(zhǔn) Dijkstra 算法是計(jì)算最短路徑的，但你有想過(guò)為什么 Dijkstra 算法不允許存在負(fù)權(quán)重邊么？

因?yàn)?Dijkstra 計(jì)算最短路徑的正確性依賴一個(gè)前提：路徑中每增加一條邊，路徑的總權(quán)重就會(huì)增加。

這個(gè)前提的數(shù)學(xué)證明大家有興趣可以自己搜索一下，我這里只說(shuō)結(jié)論，其實(shí)你把這個(gè)結(jié)論反過(guò)來(lái)也是 OK 的：

如果你想計(jì)算最長(zhǎng)路徑，路徑中每增加一條邊，路徑的總權(quán)重就會(huì)減少，要是能夠滿足這個(gè)條件，也可以用 Dijkstra 算法。

你看這道題是不是符合這個(gè)條件？邊和邊之間是乘法關(guān)系，每條邊的概率都是小于 1 的，所以肯定會(huì)越乘越小。

只不過(guò)，這道題的解法要把優(yōu)先級(jí)隊(duì)列的排序順序反過(guò)來(lái)，一些 if 大小判斷也要反過(guò)來(lái)，我們直接看解法代碼吧：

double maxProbability（int n， int［］［］ edges， double［］ succProb， int start， int end） {

List《double［］》［］ graph = new LinkedList［n］;

for （int i = 0; i 《 n; i++） {

graph［i］ = new LinkedList《》（）;

}

// 構(gòu)造鄰接表結(jié)構(gòu)表示圖

for （int i = 0; i 《 edges.length; i++） {

int from = edges［i］［0］;

int to = edges［i］［1］;

double weight = succProb［i］;

// 無(wú)向圖就是雙向圖；先把 int 統(tǒng)一轉(zhuǎn)成 double，待會(huì)再轉(zhuǎn)回來(lái)

graph［from］.add（new double［］{（double）to， weight}）;

graph［to］.add（new double［］{（double）from， weight}）;

}

return dijkstra（start， end， graph）;

}

class State {

// 圖節(jié)點(diǎn)的 id

int id;

// 從 start 節(jié)點(diǎn)到達(dá)當(dāng)前節(jié)點(diǎn)的概率

double probFromStart;

State（int id， double probFromStart） {

this.id = id;

this.probFromStart = probFromStart;

}

}

double dijkstra（int start， int end， List《double［］》［］ graph） {

// 定義：probTo［i］ 的值就是節(jié)點(diǎn) start 到達(dá)節(jié)點(diǎn) i 的最大概率

double［］ probTo = new double［graph.length］;

// dp table 初始化為一個(gè)取不到的最小值

Arrays.fill（probTo， -1）;

// base case，start 到 start 的概率就是 1

probTo［start］ = 1;

// 優(yōu)先級(jí)隊(duì)列，probFromStart 較大的排在前面

Queue《State》 pq = new PriorityQueue《》（（a， b） -》 {

return Double.compare（b.probFromStart， a.probFromStart）;

}）;

// 從起點(diǎn) start 開(kāi)始進(jìn)行 BFS

pq.offer（new State（start， 1））;

while （！pq.isEmpty（）） {

State curState = pq.poll（）;

int curNodeID = curState.id;

double curProbFromStart = curState.probFromStart;

// 遇到終點(diǎn)提前返回

if （curNodeID == end） {

return curProbFromStart;

}

if （curProbFromStart 《 probTo［curNodeID］） {

// 已經(jīng)有一條概率更大的路徑到達(dá) curNode 節(jié)點(diǎn)了

continue;

}

// 將 curNode 的相鄰節(jié)點(diǎn)裝入隊(duì)列

for （double［］ neighbor ： graph［curNodeID］） {

int nextNodeID = （int）neighbor［0］;

// 看看從 curNode 達(dá)到 nextNode 的概率是否會(huì)更大

double probToNextNode = probTo［curNodeID］ * neighbor［1］;

if （probTo［nextNodeID］ 《 probToNextNode） {

probTo［nextNodeID］ = probToNextNode;

pq.offer（new State（nextNodeID， probToNextNode））;

}

}

}

// 如果到達(dá)這里，說(shuō)明從 start 開(kāi)始無(wú)法到達(dá) end，返回 0

return 0.0;

}

好了，到這里本文就結(jié)束了，總共 6000 多字，這三道例題都是比較困難的，如果你能夠看到這里，真得給你鼓掌。

還是那句話，做題在質(zhì)不在量，希望大家能夠透徹理解最基本的數(shù)據(jù)結(jié)構(gòu)，以不變應(yīng)萬(wàn)變。

責(zé)任編輯：haq