python最短路徑的求解Dijkstra算法示例代碼

更新時間：2024年11月22日 10:17:08 作者：望月12138

這篇文章主要給大家介紹了關于python最短路徑的求解Dijkstra算法的相關資料,并使用Python的heapq模塊實現(xiàn)該算法,通過示例展示了如何從節(jié)點0到節(jié)點8求解最短路徑,需要的朋友可以參考下

前言

書接上回，之前的博客使用圖論求解最短路徑，但是只使用了 Matlab 的shortestpath 函數(shù)和 python 的 nx.shortest_path 函數(shù)進行求解。本文再介紹一種算法求解最短路徑。

一、Dijkstra算法(迪克斯特拉算法)

Dijkstra算法是一種廣泛使用的單源最短路徑算法，它能夠找到一個加權圖中從一個起始節(jié)點到其他所有節(jié)點的最短路徑。這個算法最適合于邊的權重都是非負值的圖。

算法步驟

以下是Dijkstra算法的詳細步驟：

1.初始化:將源節(jié)點到自身的距離設為0，其他節(jié)點的距離設為無窮大。將所有節(jié)點標記為未訪問。

2.選擇未訪問節(jié)點中距離最小的節(jié)點：將其標記為已訪問，如果所有未訪問節(jié)點的距離都是無窮大,
算法終止。

3.更新鄰居節(jié)點的距離:對于鄰居節(jié)點，如果通過當前節(jié)點可以獲得更短的路徑，則更新其距離。

4.重復步驟2和3，直到所有節(jié)點都被訪問過或者目標節(jié)點的最短路徑已經(jīng)確定。

堆 heapq

Dijkstra算法求解最短路徑問題時，需要選擇未訪問節(jié)點中距離最小的節(jié)點。而堆可以用于高效地找到具有最小距離的節(jié)點。
heapq 是 Python 標準庫中的一個模塊，提供了堆隊列算法的實現(xiàn)，也稱為優(yōu)先隊列算法。堆是一種特殊的樹狀數(shù)據(jù)結構，可以高效地支持插入和最小值/最大值的提取操作。Python 中的 heapq 實現(xiàn)了最小堆，即堆頂元素是最小值。

基本功能下面是 heapq 中的一些基本函數(shù)及其解釋：

heapq.heappush(heap, item): 將元素 item 添加到堆中，保持堆的不變性。
heapq.heappop(heap): 彈出并返回堆中的最小元素，同時保持堆的不變性。如果堆為空，會引發(fā) IndexError。
heapq.heappushpop(heap, item): 將元素 item 添加到堆中，然后彈出并返回堆中的最小元素。這個操作是原子的，效率比分開執(zhí)行 heappush 和 heappop 更高。
heapq.heapify(iterable): 將可迭代對象轉(zhuǎn)換為堆。
heapq.nlargest(n, iterable, key=None): 返回可迭代對象中最大的 n 個元素。
heapq.nsmallest(n, iterable, key=None): 返回可迭代對象中最小的 n 個元素。

重點強調(diào)兩個函數(shù)：

heapq.heappush(heap, item): 將元素 item 添加到堆中，函數(shù)返回值是添加元素 item后的值（既包含原來的元素，也包含元素 item 。

heapq.heappop(heap): 彈出并返回堆中的最小元素，同時保持堆的不變性。函數(shù)返回值是堆中的最小元素，并且堆更新為不含有最小元素。

二、示例

求節(jié)點 0 到節(jié)點 8 的最短路徑。

表示出示例圖

# 示例圖（鄰接表表示）
graph = {
    '0': {'1': 4, '2': 8},
    '1': {'0': 4, '2': 3, '3': 8},
    '2': {'0': 8, '1': 3, '4': 1, '5': 6},
    '3': {'1': 8, '4': 2, '6': 7, '7': 4},
    '4': {'2': 1, '3': 2, '5': 6},
    '5': {'2': 6, '4': 6, '7': 2},
    '6': {'3': 7, '7': 14, '8': 9},
    '7': {'3': 4, '5': 2, '6': 14, '8': 10},
    '8': {'6': 9, '7': 10}
}

定義Dijkstra算法函數(shù)

源節(jié)點到自身的距離設為0，其他節(jié)點的距離設為無窮大

# 初始化距離字典，將所有節(jié)點的距離設為無窮大
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0

初始化父親節(jié)點（由于此時未訪問任何節(jié)點所以全部設置為 None ）

# 初始化父親節(jié)點
parent = {vertex: None for vertex in graph}

初始化要比較的節(jié)點

# 初始化優(yōu)先隊列，并將起始節(jié)點入隊
priority_queue = [(0, start)]

從起始節(jié)點開始訪問

（1）取出當前訪問節(jié)點中距離最小的節(jié)點

（2）更新該節(jié)點相鄰的節(jié)點和距離

（3）比較節(jié)點間的距離，若有更短的路徑，則更新距離和該節(jié)點的父親節(jié)點，并將該節(jié)點加入待比較的節(jié)點

while priority_queue:
    # 彈出堆中距離最小的節(jié)點
    current_distance, current_vertex = heapq.heappop(priority_queue)
    # print("距離最小的節(jié)點是:",current_distance, current_vertex, "更新后的隊列:",priority_queue)

    # 如果當前距離已經(jīng)大于已知的最短距離，則跳過
    if current_distance > distances[current_vertex]:
        continue

    # 更新相鄰節(jié)點的距離
    for neighbor, weight in graph[current_vertex].items():
        distance = current_distance + weight
        # print("相鄰節(jié)點的距離:",neighbor,distance)

        # 如果找到更短的路徑，則更新距離，并將節(jié)點加入優(yōu)先隊列
        if distance < distances[neighbor]:
            distances[neighbor] = distance
            parent[neighbor] = current_vertex
            heapq.heappush(priority_queue, (distance, neighbor))
            # print("加入后的隊列:",priority_queue)

當訪問到最后一個節(jié)點時，heapq.heappop(heap) 函數(shù)彈出堆中最小的元素，堆中元素為空，退出循環(huán)。

Dijkstra算法函數(shù)代碼

def dijkstra(graph,start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0

    # 初始化父親節(jié)點
    parent = {vertex: None for vertex in graph}
    priority_queue = [(0,start)]

    while priority_queue:
        # 彈出堆中距離最小的節(jié)點
        current_distance, current_vertex = heapq.heappop(priority_queue)
        # print("距離最小的節(jié)點是:",current_distance, current_vertex, "更新后的隊列:",priority_queue)

        # 如果當前距離已經(jīng)大于已知的最短距離，則跳過
        if current_distance > distances[current_vertex]:
            continue

        # 更新相鄰節(jié)點的距離
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            # print("相鄰節(jié)點的距離:",neighbor,distance)

            # 如果找到更短的路徑，則更新距離，并將節(jié)點加入優(yōu)先隊列
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                parent[neighbor] = current_vertex
                heapq.heappush(priority_queue, (distance, neighbor))
                # print("加入后的隊列:",priority_queue)
    return distances, parent

函數(shù)返回值：從起始點到每個節(jié)點的最短距離，和每個節(jié)點對應的父親節(jié)點。

根據(jù)父親節(jié)點，回溯最短路徑

訪問所有節(jié)點后得到的結果：

要求從 0 到 8 的最短距離，就從 8 開始回溯，8 的父親節(jié)點是 7 ，7 的父親節(jié)點是 3 ，3 的父親節(jié)點是 4 ，4 的父親節(jié)點是 2 ，2 的父親節(jié)點是 1 ，1 的父親節(jié)點是 0 ；所以從 0 到 8 的最短路徑為： 0 —> 1 —> 2 —> 4 —> 3 —> 7 —> 8

代碼如下：

# 輸出路徑回溯
def get_path(parent, start, end):
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = parent[current]
    path.reverse()
    return path

三、python 代碼

import heapq

graph = {
    '0': {'1': 4, '2': 8},
    '1': {'0': 4, '2': 3, '3': 8},
    '2': {'0': 8, '1': 3, '4': 1, '5': 6},
    '3': {'1': 8, '4': 2, '6': 7, '7': 4},
    '4': {'2': 1, '3': 2, '5': 6},
    '5': {'2': 6, '4': 6, '7': 2},
    '6': {'3': 7, '7': 14, '8': 9},
    '7': {'3': 4, '5': 2, '6': 14, '8': 10},
    '8': {'6': 9, '7': 10}
}

def dijkstra(graph,start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0

    # 初始化父親節(jié)點
    parent = {vertex: None for vertex in graph}
    priority_queue = [(0,start)]

    while priority_queue:
        # 彈出堆中距離最小的節(jié)點
        current_distance, current_vertex = heapq.heappop(priority_queue)
        # print("距離最小的節(jié)點是:",current_distance, current_vertex, "更新后的隊列:",priority_queue)

        # 如果當前距離已經(jīng)大于已知的最短距離，則跳過
        if current_distance > distances[current_vertex]:
            continue

        # 更新相鄰節(jié)點的距離
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            # print("相鄰節(jié)點的距離:",neighbor,distance)

            # 如果找到更短的路徑，則更新距離，并將節(jié)點加入優(yōu)先隊列
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                parent[neighbor] = current_vertex
                heapq.heappush(priority_queue, (distance, neighbor))
                # print("加入后的隊列:",priority_queue)
    return distances, parent

distances, parent = dijkstra(graph, '0')
# print(parent)
# print(distances)

# 輸出路徑回溯
def get_path(parent, start, end):
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = parent[current]
    path.reverse()
    return path

end_node = '8'
path = get_path(parent, '0', end_node)
print(f"從節(jié)點 '0' 到節(jié)點 {end_node} 的路徑:", path)

運行結果：

總結

本文說明了如何使用Dijkstra算法求解最短路徑的問題，并使用python進行了代碼編寫。

到此這篇關于python最短路徑的求解Dijkstra算法的文章就介紹到這了,更多相關python最短路徑求解Dijkstra算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

詳解Python sys.argv使用方法
在本文中我們給大家詳細講解了關于Python sys.argv使用方法以及注意事項，有此需要的讀者們跟著學習下。
2019-05-05
如何利用python腳本自動部署k8s
這篇文章主要介紹了利用python腳本自動部署k8s的方法,本文通過腳本代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
2021-08-08
Python生成隨機數(shù)組的方法小結
這篇文章主要介紹了Python生成隨機數(shù)組的方法,結合實例形式總結分析了Python使用random模塊生成隨機數(shù)與數(shù)組操作相關技巧,需要的朋友可以參考下
2017-04-04
python清除字符串里非字母字符的方法
這篇文章主要介紹了python清除字符串里非字母字符的方法,涉及Python字符串正則替換操作的相關技巧,需要的朋友可以參考下
2015-07-07
python requests 庫請求帶有文件參數(shù)的接口實例
今天小編就為大家分享一篇python requests 庫請求帶有文件參數(shù)的接口實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2019-01-01
Python中pycharm編輯器界面風格修改方法
這篇文章主要介紹了Python中pycharm編輯器界面風格修改方法,本文通過圖文并茂的形式給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
2021-03-03
Python數(shù)據(jù)庫編程之pymysql詳解
本文主要介紹了Python數(shù)據(jù)庫編程中pymysql，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2023-05-05
python網(wǎng)絡編程學習筆記(六)：Web客戶端訪問
這篇文章主要介紹了python網(wǎng)絡編程之Web客戶端訪問 ,需要的朋友可以參考下
2014-06-06
OpenCV?光流Optical?Flow示例
這篇文章主要為大家介紹了OpenCV?光流Optical?Flow示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
2023-04-04
關于Python調(diào)用百度語音合成SDK實現(xiàn)文字轉(zhuǎn)音頻的方法
這篇文章主要介紹了關于Python調(diào)用百度語音合成SDK實現(xiàn)文字轉(zhuǎn)音頻的方法,AipSpeech是語音合成的Python?SDK客戶端，為使用語音合成的開發(fā)人員提供了一系列的交互方法,需要的朋友可以參考下
2023-07-07