最短路径python

最短路径算法是解决图论问题中常见的任务之一，其中最著名的算法是Dijkstra算法和Bellman-Ford算法。以下是用Python实现这两个算法的示例代码：

Dijkstra算法实现：

import sys

def dijkstra(graph, start):
    # 初始化距离字典和已访问节点集合
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    visited = set()

    while len(visited) < len(graph):
        # 找到当前最短距离的节点
        min_node = None
        for node in graph:
            if node not in visited and (min_node is None or dist[node] < dist[min_node]):
                min_node = node

        # 更新最短距离和路径
        for neighbor, weight in graph[min_node].items():
            if dist[min_node] + weight < dist[neighbor]:
                dist[neighbor] = dist[min_node] + weight

        visited.add(min_node)

    return dist

# 示例图
graph = {
    'A': {'B': 5, 'C': 2},
    'B': {'D': 1, 'E': 6},
    'C': {'B': 1, 'D': 4},
    'D': {'E': 1},
    'E': {}
}

start_node = 'A'
distances = dijkstra(graph, start_node)
print(distances)

Bellman-Ford算法实现：

def bellman_ford(graph, start):
    # 初始化距离字典
    dist = {node: float('inf') for node in graph}
    dist[start] = 0

    # 重复更新距离直到收敛
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if dist[node] + weight < dist[neighbor]:
                    dist[neighbor] = dist[node] + weight

    # 检查是否存在负权回路
    for node in graph:
        for neighbor, weight in graph[node].items():
            if dist[node] + weight < dist[neighbor]:
                raise ValueError("存在负权回路")

    return dist

# 示例图
graph = {
    'A': {'B': 5, 'C': 2},
    'B': {'D': 1, 'E': 6},
    'C': {'B': 1, 'D': 4},
    'D': {'E': 1},
    'E': {}
}

start_node = 'A'
distances = bellman_ford(graph, start_node)
print(distances)

这些代码可以根据给定的图和起始节点计算最短路径。请注意，示例代码中的图是用字典表示的邻接表。键表示节点，值表示与该节点相连的邻居节点及其权重。