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

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

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

前言

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

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

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

算法步驟

以下是Dijkstra算法的詳細(xì)步驟：

1.初始化:將源節(jié)點(diǎn)到自身的距離設(shè)為0，其他節(jié)點(diǎn)的距離設(shè)為無(wú)窮大。將所有節(jié)點(diǎn)標(biāo)記為未訪問(wèn)。

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

3.更新鄰居節(jié)點(diǎn)的距離:對(duì)于鄰居節(jié)點(diǎn)，如果通過(guò)當(dāng)前節(jié)點(diǎn)可以獲得更短的路徑，則更新其距離。

4.重復(fù)步驟2和3，直到所有節(jié)點(diǎn)都被訪問(wèn)過(guò)或者目標(biāo)節(jié)點(diǎn)的最短路徑已經(jīng)確定。

堆 heapq

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

基本功能下面是 heapq 中的一些基本函數(shù)及其解釋?zhuān)?/p>

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

重點(diǎn)強(qiáng)調(diào)兩個(gè)函數(shù)：

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

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

二、示例

求節(jié)點(diǎn) 0 到節(jié)點(diǎn) 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é)點(diǎn)到自身的距離設(shè)為0，其他節(jié)點(diǎn)的距離設(shè)為無(wú)窮大

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

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

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

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

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

從起始節(jié)點(diǎn)開(kāi)始訪問(wèn)

（1）取出當(dāng)前訪問(wèn)節(jié)點(diǎn)中距離最小的節(jié)點(diǎn)

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

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

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

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

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

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

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

Dijkstra算法函數(shù)代碼

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

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

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

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

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

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

函數(shù)返回值：從起始點(diǎn)到每個(gè)節(jié)點(diǎn)的最短距離，和每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的父親節(jié)點(diǎn)。

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

訪問(wèn)所有節(jié)點(diǎn)后得到的結(jié)果：

要求從 0 到 8 的最短距離，就從 8 開(kāi)始回溯，8 的父親節(jié)點(diǎn)是 7 ，7 的父親節(jié)點(diǎn)是 3 ，3 的父親節(jié)點(diǎn)是 4 ，4 的父親節(jié)點(diǎn)是 2 ，2 的父親節(jié)點(diǎn)是 1 ，1 的父親節(jié)點(diǎn)是 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é)點(diǎn)
    parent = {vertex: None for vertex in graph}
    priority_queue = [(0,start)]

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

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

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

            # 如果找到更短的路徑，則更新距離，并將節(jié)點(diǎn)加入優(yōu)先隊(duì)列
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                parent[neighbor] = current_vertex
                heapq.heappush(priority_queue, (distance, neighbor))
                # print("加入后的隊(duì)列:",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é)點(diǎn) '0' 到節(jié)點(diǎn) {end_node} 的路徑:", path)

運(yùn)行結(jié)果：