欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間：2024年11月22日 10:17:08   作者：望月12138  
這篇文章主要給大家介紹了關(guān)于python最短路徑的求解Dijkstra算法的相關(guān)資料,并使用Python的heapq模塊實(shí)現(xiàn)該算法,通過示例展示了如何從節(jié)點(diǎn)0到節(jié)點(diǎn)8求解最短路徑,需要的朋友可以參考下

前言

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

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

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

算法步驟

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

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

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

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

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

堆 heapq

  • Dijkstra算法求解最短路徑問題時，需要選擇未訪問節(jié)點(diǎn)中距離最小的節(jié)點(diǎn)。而堆可以用于高效地找到具有最小距離的節(jié)點(diǎn)。
  • heapq 是 Python 標(biāo)準(zhǔn)庫中的一個模塊，提供了堆隊列算法的實(shí)現(xiàn)，也稱為優(yōu)先隊列算法。堆是一種特殊的樹狀數(shù)據(jù)結(jié)構(gòu)，可以高效地支持插入和最小值/最大值的提取操作。Python 中的 heapq 實(shí)現(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ǎn)強(qiáng)調(diào)兩個函數(shù)：

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

heapq.heappop(heap): 彈出并返回堆中的最小元素，同時保持堆的不變性。函數(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è)為無窮大
# 初始化距離字典，將所有節(jié)點(diǎn)的距離設(shè)為無窮大
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
  • 初始化父親節(jié)點(diǎn)（由于此時未訪問任何節(jié)點(diǎn)所以全部設(shè)置為 None ）
# 初始化父親節(jié)點(diǎn)
parent = {vertex: None for vertex in graph}
  • 初始化要比較的節(jié)點(diǎn)
# 初始化優(yōu)先隊列，并將起始節(jié)點(diǎn)入隊
priority_queue = [(0, start)]
  • 從起始節(jié)點(diǎn)開始訪問

（1）取出當(dāng)前訪問節(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, "更新后的隊列:",priority_queue)

    # 如果當(dāng)前距離已經(jīng)大于已知的最短距離，則跳過
    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)先隊列
        if distance < distances[neighbor]:
            distances[neighbor] = distance
            parent[neighbor] = current_vertex
            heapq.heappush(priority_queue, (distance, neighbor))
            # print("加入后的隊列:",priority_queue)

當(dāng)訪問到最后一個節(jié)點(diǎn)時，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, "更新后的隊列:",priority_queue)

        # 如果當(dāng)前距離已經(jīng)大于已知的最短距離，則跳過
        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)先隊列
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                parent[neighbor] = current_vertex
                heapq.heappush(priority_queue, (distance, neighbor))
                # print("加入后的隊列:",priority_queue)
    return distances, parent

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

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

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

要求從 0 到 8 的最短距離，就從 8 開始回溯，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, "更新后的隊列:",priority_queue)

        # 如果當(dāng)前距離已經(jīng)大于已知的最短距離，則跳過
        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)先隊列
            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é)點(diǎn) '0' 到節(jié)點(diǎn) {end_node} 的路徑:", path)

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

總結(jié)

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

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

相關(guān)文章

最新評論