博客

python实现dijkstra最短路由算法

  • Post category:Python

下面是详细讲解“Python实现Dijkstra最短路径算法”的完整攻略，包含两个示例说明。

Dijkstra最短路径算法简介

Dijkstra最短路径算法是一种用于计算带权图中最短路径的贪心算法。该算法从起点开始，逐步扩展到其他节点，直到到达终点为止。在每个步骤中，它选择距离起点最近的节点，并更新与该节点相邻的节点的距离。

Dijkstra最短路径算法实现

下面是Python实现Dijkstra最短路径算法的代码：

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [(0, start)]
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    return distances

dijkstra函数接受一个字典graph，表示带权图，以及一个起始节点start。该函数返回一个字典，表示从起始节点到每个节点的最短距离。

该函数首先将所有节点的距离初始化为无穷大，将起始节点的距离初始化为0，并将其添加到一个堆队列中。然后，它循环直到队列为空。对于每个节点，它将其从队列中弹出，并将其距离与当前已知的距离进行比较。如果当前距离大于已知距离，则跳过该节点。否则，它将更新与该节点相邻的节点的距离，并将它们添加到队列中。

示例1：计算带权图中的最短路径

让我们使用dijkstra函数计算带权图中的最短路径：

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
distances = dijkstra(graph, 'A')
print(distances)

这将输出从节点A到其他节点的最短距离。

示例2：计算地图上的最短路径

让我们使用dijkstra函数计算地图上两个城市之间的最短路径：

import json
import requests

def get_distance(origin, destination):
    url = f'https://maps.googleapis.com/maps/api/distancematrix/json?units=imperial&origins={origin}&destinations={destination}&key=YOUR_API_KEY'
    response = requests.get(url)
    data = json.loads(response.text)
    return data['rows'][0]['elements'][0]['distance']['value'] / 1000

graph = {
    'New York': {},
    'Los Angeles': {},
    'Chicago': {},
    'Houston': {},
    'Phoenix': {},
    'Philadelphia': {},
    'San Antonio': {},
    'San Diego': {},
    'Dallas': {},
    'San Jose': {}
}
for city1 in graph:
    for city2 in graph:
        if city1 != city2:
            distance = get_distance(city1, city2)
            graph[city1][city2] = distance

distances = dijkstra(graph, 'New York')
print(distances)

这将输出从纽约到其他城市的最短距离。

请注意，您需要将YOUR_API_KEY替换为您自己的Google Maps API密钥。

希望这个攻略能够帮助你理解如何在Python中实现Dijkstra最短路径算法！

Tags: ,