目錄

前言

1. 介紹

2. 加權(quán)圖

2.1 概念

3. 最短路徑 -- Dijkstra 算法

3.1 歷史

3.2 Dijkstra 算法的基本思路

3.3?Dijkstra 算法圖解

4.? python中dijkstra算法的實現(xiàn)

5. 總結(jié)?

前言

前兩章我們講到了關(guān)于圖的基本知識，和廣度/深度優(yōu)先搜索。

本章，我們將介紹加權(quán)圖和最短路徑的相關(guān)知識。

1. 介紹

最短路徑是圖論中常見問題。

最短路徑是指在一個圖中找到兩個節(jié)點之間的最短路徑。

最短路徑算法常見的有?floyd算法（弗洛伊德算法）和?dijkstra算法（迪杰斯特拉）。本文只介紹dijkstra算法。
最短路徑運(yùn)用非常廣泛，比如在導(dǎo)航系統(tǒng)中，確定兩個地點間哪條路線最短；在網(wǎng)絡(luò)路由中，路由器需要找到最短路徑來轉(zhuǎn)發(fā)數(shù)據(jù)包。

2. 加權(quán)圖

2.1 概念

加權(quán)圖是指每條邊都帶有權(quán)重的圖。每個邊的權(quán)重可以表示兩個頂點之間的距離、成本或任何其他可以量化的指標(biāo)。實際上，邊的權(quán)重可以為負(fù)數(shù)，但是本章只介紹最短路徑中的dijkstra算法且這種算法的前提條件就是權(quán)重不能為負(fù)數(shù)，所以不將負(fù)數(shù)的權(quán)重拓展到本文。

下面的加權(quán)圖中，每一個紅色的數(shù)字都代表著那條邊的權(quán)重。

3. 最短路徑 -- Dijkstra 算法

3.1 歷史

這個算法由荷蘭杰出計算機(jī)科學(xué)家、軟件工程師艾茲赫爾·戴克斯特拉 (Edsger W. Dijkstra)（1930年5月11日~2002年8月6日）發(fā)明。他是計算機(jī)先驅(qū)之一，與高德納（Donald Ervin Knuth）并稱為我們這個時代最偉大的計算機(jī)科學(xué)家。

從 Rotterdam 到 Groningen 的最短路線是什么？我花了大概 20 分鐘時間設(shè)計了這個尋找最短路徑的算法。一天早上我正和我年輕的未婚妻在 Amsterdam 逛街，覺得有點累了，我們就坐在咖啡廳的露臺上喝了一杯咖啡，我在想是否能夠解決這個問題，然后，我設(shè)計出了這個最短路徑算法。我說過，這是一個 20 分鐘的設(shè)計。事實上，三年之后的 1959 年它才被發(fā)布，現(xiàn)在看來依然很不錯，其原因之一是我當(dāng)時設(shè)計的時候沒有紙和筆，從而不得不極力避免所有可避免的復(fù)雜性。最終，令我驚訝的是，這個算法成為了我成名的基石之一。

節(jié)選自文章《An interview with Edsger W. Dijkstra》

3.2 Dijkstra 算法的基本思路

首先將起始節(jié)點的距離標(biāo)記為0，其他節(jié)點的距離因為還不確定所以先需要標(biāo)記為無窮大。

然后，在圖中找到距離起始節(jié)點最近的節(jié)點，更新其相鄰節(jié)點的距離，距離為從起始節(jié)點到該節(jié)點的距離加上該節(jié)點到相鄰節(jié)點的距離。

不斷循環(huán)此過程，直到所有節(jié)點都被訪問過。

這就是Dijkstra 算法的基本思路。

3.3?Dijkstra 算法圖解

在下面這個圖的基礎(chǔ)上，我們可以一步一步來分析Dijkstra 算法的過程。

我們的目的是用此算法找到節(jié)點D到任意其他節(jié)點的最短路徑。

1. 首先我們創(chuàng)建一個表格來記錄節(jié)點D到所有節(jié)點的距離（自身為0，其余初始化為無窮大），還需要記錄最短路徑中每個節(jié)點的先驅(qū)節(jié)點（初始化為空）。最后需要一個flag去標(biāo)記已經(jīng)訪問過的節(jié)點（初始化為F）。

2. 檢查所有未標(biāo)記節(jié)點中距離最短的節(jié)點，就是節(jié)點D，將其加入最短路徑中，并標(biāo)記。?

3. 更新經(jīng)過節(jié)點D的相鄰節(jié)點距離到起始節(jié)點的距離，也就是D-B，D-E，D-G的距離，分別是4，1，5，同時使節(jié)點D作為他們的先驅(qū)節(jié)點。

4. 檢查所有未標(biāo)記節(jié)點中距離最短的節(jié)點，就是節(jié)點E，將其加入最短路徑中，并標(biāo)記。

5.??更新經(jīng)過節(jié)點E的相鄰節(jié)點到起始節(jié)點的距離，也就是D-E-B，D-E-C，D-E-F，D-E-G和D-E-H的距離，分別是9，11，12，7,13。但是因為D-B和D-G的路徑在上一步已經(jīng)更新過了，并且距離要小于D-E-B和D-E-G的距離，所以不更新節(jié)點B和節(jié)點G的距離，更新節(jié)點C，F(xiàn)和H的距離，同時使節(jié)點E作為他們的先驅(qū)節(jié)點。

6.??檢查所有未標(biāo)記節(jié)點中距離最短的節(jié)點，就是節(jié)點B，將其加入最短路徑中，并標(biāo)記。

7.?更新經(jīng)過節(jié)點B的相鄰節(jié)點到起始節(jié)點的距離，也就是D-B-A，距離為6，同時使節(jié)點B作為他的先驅(qū)節(jié)點。?

8.??檢查所有未標(biāo)記節(jié)點中距離最短的節(jié)點，就是節(jié)點G，將其加入最短路徑中，并標(biāo)記。

9.???更新經(jīng)過節(jié)點G的相鄰節(jié)點到起始節(jié)點的距離，也就是D-G-E，距離為11，但是因為之前保存過D-E的距離為1，很明顯D-E的距離要更近一些，所以不更新表格。

10.?檢查所有未標(biāo)記節(jié)點中距離最短的節(jié)點，就是節(jié)點A，將其加入最短路徑中，并標(biāo)記。

11.??更新經(jīng)過節(jié)點A的相鄰節(jié)點到起始節(jié)點的距離，也就是D-B-A-C，距離為15，但是因為之前保存過D-E-C的距離為11，D-E-C的距離要近于D-B-A-C，所以不更新表格。

12.??檢查所有未標(biāo)記節(jié)點中距離最短的節(jié)點，就是節(jié)點C，將其加入最短路徑中，并標(biāo)記。

13.?更新經(jīng)過節(jié)點C的相鄰節(jié)點到起始節(jié)點的距離，也就是D-E-C-F，距離為14，但是因為之前保存過D-E-F的距離為12，D-E-F的距離要近于D-E-C-F，所以不更新表格。?

14.?檢查所有未標(biāo)記節(jié)點中距離最短的節(jié)點，就是節(jié)點F，將其加入最短路徑中，并標(biāo)記。

15.?更新經(jīng)過節(jié)點F的相鄰節(jié)點到起始節(jié)點的距離，也就是D-E-F-H，距離為29，但是因為之前保存過D-E-H的距離為13，D-E-H的距離要近于D-E-F-H，所以不更新表格。

16.? ?檢查所有未標(biāo)記節(jié)點中距離最短的節(jié)點，就是節(jié)點H，將其加入最短路徑中，并標(biāo)記。

17. 算法結(jié)束，此時我們擁有了從出發(fā)點D到任意一個節(jié)點的距離以及路徑。最短路徑可以根據(jù)先驅(qū)節(jié)點倒推出來，比如從D到H的最短距離為13，最短路徑為D-E-H。

最短距離：看節(jié)點H，發(fā)現(xiàn)與起始點D的最短距離為13。
最短路徑：看H的先驅(qū)節(jié)點，發(fā)現(xiàn)是E，在看E的先驅(qū)節(jié)點，發(fā)現(xiàn)是D。那么，從D到H的最短路徑就是D-E-H了。?

4.? python中dijkstra算法的實現(xiàn)

import sys

def dijkstra(graph, start_node):
    unvisited_nodes = {node: sys.maxsize for node in graph}  # 初始化所有節(jié)點距離為無窮大
    unvisited_nodes[start_node] = 0  # 起始節(jié)點距離為0
    shortest_paths = {start_node: (0, [])}  # 起始節(jié)點的路徑和距離

    while unvisited_nodes:
        current_node = min(unvisited_nodes, key=unvisited_nodes.get)  # 找到未訪問節(jié)點中距離最小的節(jié)點
        current_distance = unvisited_nodes[current_node]

        for neighbor, distance in graph[current_node].items():
            if neighbor not in unvisited_nodes: continue  # 已訪問過的節(jié)點跳過
            new_distance = current_distance + distance
            if new_distance < unvisited_nodes[neighbor]:  # 如果找到更短路徑，更新
                unvisited_nodes[neighbor] = new_distance
                shortest_paths[neighbor] = (new_distance, shortest_paths[current_node][1] + [current_node])  # 更新路徑和距離

        unvisited_nodes.pop(current_node)  # 當(dāng)前節(jié)點已訪問過，從未訪問節(jié)點中刪除

    return shortest_paths  # 返回最短路徑和距離

# 測試Dijkstra算法
if __name__ == "__main__":
    graph = {
        'A': {'B': 2, 'C': 9},
        'B': {'A': 2, 'D': 4, 'E': 8},
        'C': {'A': 9, 'E': 10, 'F': 3},
        'D': {'B': 4, 'E': 1, 'G': 5},
        'E': {'B': 8, 'C': 10, 'D': 1, 'F': 11, 'G': 6, 'H': 12},
        'F': {'C': 3, 'E': 11, 'H': 17},
        'G': {'D': 5, 'E': 6},
        'H': {'E': 12, 'F': 17},
    }
    start_node = 'D'
    shortest_paths = dijkstra(graph, start_node)
    print(shortest_paths)

首先我創(chuàng)建了一個上面舉例子的圖，然后設(shè)置頂點D為起始頂點。

運(yùn)行上面代碼之后會打印出：

{'D': (0, []), 'B': (4, ['D']), 'E': (1, ['D']), 'G': (5, ['D']), 'C': (11, ['D', 'E']), 'F': (12, ['D', 'E']), 'H': (13, ['D', 'E']), 'A': (6, ['D', 'B'])}

我們可以很明顯找到從D到任意一個頂點的最短路徑和距離。

5. 總結(jié)?

Dijkstra算法是非常經(jīng)典的最短路徑算法，這種算法可以找到起始頂點與圖中任意一個頂點的最短路徑。但是其也有限制，圖的權(quán)重必須不能有負(fù)數(shù)。如果圖的權(quán)重帶有負(fù)數(shù)，則需要使用Bellman-ford算法，如果想要確定任意兩點的最短路徑，則需要使用floyd算法。

ps. 本來打算把最小生成樹也在這一章總結(jié)的，但是最近學(xué)校事情比較多，只能往后拖一拖了TOT?

希望大家能從這篇文章中對Dijkstra算法有更清晰的了解，如果我有什么地方講的不對，歡迎大家指出！文章來源地址http://www.zghlxwxcb.cn/news/detail-518366.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法 —— 最短路徑Dijkstra算法（迪杰斯特拉）詳細(xì)圖解以及python實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！