Python最短路径(Python实现最短路径算法)

Dijkstra算法是一种求解最短路径问题的经典算法。

以下是使用Python实现Dijkstra算法的一个示例：

import heapq
def dijkstra(graph, start, end):
    # 初始化距离字典
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    # 初始化优先队列
    priority_queue = [(0, start)]
    while priority_queue:
        # 获取当前距离最短的节点
        current_distance, current_node = heapq.heappop(priority_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(priority_queue, (distance, neighbor))
    return distances[end]
# 示例图（使用字典表示）
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}
}
# 计算最短路径
shortest_path = dijkstra(graph, 'A', 'D')
print("最短路径长度:", shortest_path)
import heapq

def dijkstra(graph, start, end):
    # 初始化距离字典
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0

    # 初始化优先队列
    priority_queue = [(0, start)]

    while priority_queue:
        # 获取当前距离最短的节点
        current_distance, current_node = heapq.heappop(priority_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(priority_queue, (distance, neighbor))

    return distances[end]

# 示例图（使用字典表示）
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}
}

# 计算最短路径
shortest_path = dijkstra(graph, 'A', 'D')
print("最短路径长度:", shortest_path)
import heapq

def dijkstra(graph, start, end):
    # 初始化距离字典
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0

    # 初始化优先队列
    priority_queue = [(0, start)]

    while priority_queue:
        # 获取当前距离最短的节点
        current_distance, current_node = heapq.heappop(priority_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(priority_queue, (distance, neighbor))

    return distances[end]

# 示例图（使用字典表示）
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}
}

# 计算最短路径
shortest_path = dijkstra(graph, 'A', 'D')
print("最短路径长度:", shortest_path)

在这个示例中，我们定义了一个名为dijkstra的函数，它接受一个表示图的字典、起始节点和目标节点。

我们使用heapq库实现优先队列，以便高效地获取当前距离最短的节点。

首先，我们初始化一个距离字典，将所有节点的距离设置为无穷大，并将起始节点的距离设置为0。

接下来，我们将起始节点添加到优先队列中，并在循环中处理队列中的每个节点。

对于每个节点，我们遍历其相邻节点并更新距离。当优先队列为空时，算法结束。

在这个示例中，我们使用了一个简单的有向图。可以根据需要修改图的表示以求解更复杂的最短路径问题。