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包中__init__.py文件的作用與用法實例詳解
我們新建python包時常常會看到一個__init _.py文件,下面這篇文章主要給大家介紹了關于Python包中__init__.py文件的作用與用法的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下
2022-06-06
python自動化測試之破解滑動驗證碼
這篇文章介紹了python自動化破解之破解滑動驗證碼的解決方案，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
2022-07-07
對python中Matplotlib的坐標軸的坐標區(qū)間的設定實例講解
今天小編就為大家分享一篇對python中Matplotlib的坐標軸的坐標區(qū)間的設定實例講解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2018-05-05
Python批量修改xml的坐標值全部轉(zhuǎn)為整數(shù)的實例代碼
這篇文章主要介紹了Python批量修改xml的坐標值全部轉(zhuǎn)為整數(shù)的實例代碼,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
2020-11-11
解決python寫的windows服務不能啟動的問題
使用py2exe生成windows服務在win7下可以正常運行，但是到了xp下面可以安裝，但是無法啟動
2014-04-04
python讀取json文件并將數(shù)據(jù)插入到mongodb的方法
這篇文章主要介紹了python讀取json文件并將數(shù)據(jù)插入到mongodb的方法,實例分析了Python操作json及mongodb數(shù)據(jù)庫的技巧,需要的朋友可以參考下
2015-03-03
基于python修改srt字幕的時間軸
這篇文章主要介紹了基于python修改srt字幕的時間軸,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2020-02-02
Python3 解決讀取中文文件txt編碼的問題
今天小編就為大家分享一篇Python3 解決讀取中文文件txt編碼的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2019-12-12
Python簡單I/O操作示例
這篇文章主要介紹了Python簡單I/O操作,結合實例形式分析了Python針對文件的I/O讀寫及cPickle模塊相關使用操作技巧,需要的朋友可以參考下
2019-03-03
Python實現(xiàn)二維有序數(shù)組查找的方法
這篇文章主要介紹了Python實現(xiàn)二維有序數(shù)組查找的方法,結合實例形式分析了Python二維有序數(shù)組的查找思路及具體實現(xiàn)技巧,需要的朋友可以參考下
2016-04-04