圖遍歷算法之最短路徑Dijkstra算法

一、最短路徑問(wèn)題（shortest path problem)

最短路徑問(wèn)題是圖論研究中一個(gè)經(jīng)典算法問(wèn)題，旨在尋找圖中兩節(jié)點(diǎn)或單個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)之間的最短路徑。根據(jù)問(wèn)題的不同，算法的具體形式包括：

  • 確定起點(diǎn)的最短路徑問(wèn)題，即給定起始節(jié)點(diǎn)，求該節(jié)點(diǎn)到其他剩余節(jié)點(diǎn)的最短路徑，適合使用Dijkstra算法；
  • 確定終點(diǎn)的最短路徑問(wèn)題，即給定終點(diǎn)，求其他節(jié)點(diǎn)到該終點(diǎn)的最短路徑。在無(wú)向圖中，該問(wèn)題與確定起點(diǎn)的問(wèn)題等價(jià)；在有向圖中，問(wèn)題等價(jià)于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問(wèn)題；
  • 確定起點(diǎn)終點(diǎn)的最短路徑問(wèn)題，即給定起點(diǎn)和終點(diǎn)，求兩節(jié)點(diǎn)之間的最短路徑；
  • 全局最短路徑問(wèn)題，即求圖中所有節(jié)點(diǎn)之間的最短路徑，適合使用Floyd-Warshall算法。

常用的最短路徑算法包括：Dijkstra算法，A^{\star}算法，Bellman-Ford算法，SPFA算法（Bellman-Ford算法的改進(jìn)版本），F(xiàn)loyd-Warshall算法，Johnson算法以及Bi-direction BFS算法。本文將重點(diǎn)介紹Dijkstra算法的原理以及實(shí)現(xiàn)。

二、Dijkstra算法介紹

1. 算法概覽

Dijkstra算法，翻譯作戴克斯特拉算法或迪杰斯特拉算法，于1956年由荷蘭計(jì)算機(jī)科學(xué)家艾茲赫爾.戴克斯特拉提出，用于解決賦權(quán)有向圖的單源最短路徑問(wèn)題。所謂單源最短路徑問(wèn)題是指確定起點(diǎn)，尋找該節(jié)點(diǎn)到圖中任意節(jié)點(diǎn)的最短路徑，算法可用于尋找兩個(gè)城市中的最短路徑或是解決著名的旅行商問(wèn)題。

問(wèn)題描述：在無(wú)向圖G=(V, E)中，V 為圖節(jié)點(diǎn)的集合，E為節(jié)點(diǎn)之間連線邊的集合。假設(shè)每條邊E_i的權(quán)重為\omega_i，找到由頂點(diǎn)V_0到其余各個(gè)節(jié)點(diǎn)的最短路徑（單源最短路徑）。

2. 算法描述

G=(V, E)為帶權(quán)無(wú)向圖，圖中頂點(diǎn)V分為兩組，第一組為已求出最短路徑的頂點(diǎn)集合（用S表示）。初始時(shí)S只有源點(diǎn)，當(dāng)求得一條最短路徑時(shí)，便將新增頂點(diǎn)添加進(jìn)S，直到所有頂點(diǎn)加入S中，算法結(jié)束。第二組為未確定最短路徑頂點(diǎn)集合（用U表示），隨著S中頂點(diǎn)增加，U中頂點(diǎn)逐漸減少。

  • 初始化：S只包含起點(diǎn)s， U包含s外的其他頂點(diǎn)。U中的距離為起點(diǎn)s到頂點(diǎn)的距離。若s與v相鄰，則U中頂點(diǎn)v距離為(s,v)的邊緣權(quán)重；若s與v不相鄰，則v的距離為\infty;
  • 更新S和U：從U中選出距離值最小的頂點(diǎn)k，并將頂點(diǎn)k添加至S；同時(shí)，從U中移除k；
  • 更新U中頂點(diǎn)到起點(diǎn)s的距離：由于S中添加了k，利用k進(jìn)一步更新s到其他頂點(diǎn)的距離，存在(s, v)>(s,k)+(k,v)的可能性；
  • 反復(fù)迭代：重復(fù)第二步和第三步，直到遍歷完所有節(jié)點(diǎn)。

3. 算法示例

以下圖為例，對(duì)Dijkstra算法的工作流程進(jìn)行演示（以頂點(diǎn)D為起點(diǎn)）：

圖1. 有權(quán)無(wú)向圖G

注：
01）S是已計(jì)算出最短路徑的頂點(diǎn)集合；
02）U是未計(jì)算出最短路徑的頂點(diǎn)集合；
03）C(3)表示頂點(diǎn)C到頂點(diǎn)D的最短距離為3
第1步：選取頂點(diǎn)D添加進(jìn)S
S=\{D(0) \}
U=\{A(\infty), B(\infty), C(3), E(4), F(\infty), G(\infty)\}

圖2. 第1步

第2步：選取頂點(diǎn)C添加進(jìn)S，更新U中頂點(diǎn)最短距離
S=\{D(0), C(3) \}
B(\infty)->C(3)+10=13
F(\infty)->C(3)+6=9)
U=\{A(\infty), B(13), E(4), F(9), G(\infty)\}

圖3. 第2步

第3步：選取頂點(diǎn)E添加進(jìn)S，更新U中頂點(diǎn)最短距離
S=\{D(0), C(3) , E(4)\}
F(9)->E(4)+2=6
G(\infty)->E(4)+8=12
U=\{A(\infty), B(13), F(6), G(12) \}

圖4. 第3步

第4步：選取頂點(diǎn)F添加進(jìn)S，更新U中頂點(diǎn)最短距離
S=\{D(0), C(3) , E(4), F(6) \}
B(13)->F(6)+7=13
G(12)->F(6)+9=15
A(\infty)->F(6)+16=22
U=\{A(22), B(13), G(12) \}

圖5. 第4步

第5步：選取頂點(diǎn)G添加進(jìn)S，更新U中頂點(diǎn)最短距離
S=\{D(0), C(3) , E(4), F(6), G(12)\}
A(22)->G(12)+14=26
U=\{A(22), B(13)\}

圖6. 第5步

第6步：選取頂點(diǎn)B添加進(jìn)S，更新U中頂點(diǎn)最短距離
S=\{D(0), C(3) , E(4), F(6), G(12), B(13)\}
A(22)->B(13)+12=25
U=\{ A(22)\}

圖7. 第6步

第7步：選取頂點(diǎn)B添加進(jìn)S，更新U中頂點(diǎn)最短距離
S=\{D(0), C(3) , E(4), F(6), G(12), B(13), A(22)\}

圖8. 第7步

三、Dijkstra算法的R及Python軟件實(shí)現(xiàn)

1. R實(shí)現(xiàn)Dijkstra算法：igraph包中shortest.paths函數(shù)

示例：node編號(hào)1-7分別代表A,B,C,D,E,F,G

require(igraph)
graph_matrix<-as.matrix(read.table(text=
   "node x1 x2 x3 x4 x5 x6 x7
     1 0  12 NA NA NA 16 14
     2 12 0 10 NA NA 7 NA
     3 NA 10 0 3 5 6 NA
     4 NA NA 3 0 4 NA NA
     5 NA NA 5 4 0 2 8
     6 16 7 6 NA 2 0 9
     7 14 NA NA NA 8 9 0
   ", header=T))
nms<-graph_matrix[,1]
mat<-graph_matrix[,-1]
colnames(mat)<-rownames(mat)<-nms
mat[is.na(mat)]<-0
# create graph from adjacency matrix
g <- graph.adjacency(mat, weighted=TRUE)
# Get all path distances
(s.paths <- shortest.paths(g, algorithm = "dijkstra"))
(s.paths <- shortest.paths(g,4, algorithm = "dijkstra"))

(s.paths <- shortest.paths(g, algorithm = "dijkstra"))輸出結(jié)果：

   1  2  3  4  5  6  7
1  0 12 22 22 18 16 14
2 12  0 10 13  9  7 16
3 22 10  0  3  5  6 13
4 22 13  3  0  4  6 12
5 18  9  5  4  0  2  8
6 16  7  6  6  2  0  9
7 14 16 13 12  8  9  0

(s.paths <- shortest.paths(g,4, algorithm = "dijkstra"))輸出結(jié)果：

   1  2 3 4 5 6  7
4 22 13 3 0 4 6 12

2. Python語(yǔ)言實(shí)現(xiàn)Dijkstra算法：networkx 模塊

示例：

from dijkstar import Graph, find_path
graph=Graph()
graph.add_edge(1,2,{'cost':12})
graph.add_edge(1,6,{'cost':16})
graph.add_edge(1,7,{'cost':14})
graph.add_edge(2,3,{'cost':10})
graph.add_edge(2,6,{'cost':7})
graph.add_edge(2,1,{'cost':12})
graph.add_edge(3,2,{'cost':10})
graph.add_edge(3,4,{'cost':3})
graph.add_edge(3,5,{'cost':5})
graph.add_edge(3,6,{'cost':6})
graph.add_edge(4,3,{'cost':3})
graph.add_edge(4,5,{'cost':4})
graph.add_edge(3,5,{'cost':5})
graph.add_edge(3,6,{'cost':6})
graph.add_edge(4,3,{'cost':3})
graph.add_edge(4,5,{'cost':4})
graph.add_edge(5,3,{'cost':5})
graph.add_edge(5,4,{'cost':4})
graph.add_edge(5,6,{'cost':2})
graph.add_edge(5,7,{'cost':8})

graph.add_edge(6,1,{'cost':16})
graph.add_edge(6,2,{'cost':7})
graph.add_edge(6,3,{'cost':6})
graph.add_edge(6,5,{'cost':2})
graph.add_edge(6,7,{'cost':9})
graph.add_edge(7,1,{'cost':14})
graph.add_edge(7,5,{'cost':8})
graph.add_edge(7,6,{'cost':9})

cost_func = lambda u, v, e, prev_e: e['cost']
find_path(graph, 4, 7, cost_func=cost_func)

找到D（4）到G（7）的最短路徑：

PathInfo(nodes=[4, 5, 7], edges=[{'cost': 4}, {'cost': 8}], costs=[4, 8], total_cost=12)

參考資料：

[1] 維基百科，最短路徑問(wèn)題：https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98；
[2]CSDN，Dijkstra算法原理：https://blog.csdn.net/yalishadaa/article/details/55827681;
[3]RDocumentation: https://www.rdocumentation.org/packages/RNeo4j/versions/1.6.4/topics/dijkstra;
[4]RDocumentation: https://www.rdocumentation.org/packages/igraph/versions/0.1.1/topics/shortest.paths;
[5]Pypi: https://pypi.org/project/Dijkstar/

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容