python实现最小路径的三种算法代码

很高兴回答您的问题！以下是三种常见的最小路径算法的Python实现代码：

1. Dijkstra算法：

import heapq

def dijkstra(graph, start):
    # 初始化起点到各个顶点的距离为无穷大
    dist = {v: float('inf') for v in graph}
    # 起点到自身的距离为0
    dist[start] = 0
    # 建立最小堆
    heap = [(0, start)]
    while heap:
        # 弹出最小距离的顶点
        (d, v) = heapq.heappop(heap)
        # 如果当前顶点已经访问过，跳过
        if d > dist[v]:
            continue
        # 遍历该顶点的所有邻居
        for neighbor, weight in graph[v].items():
            # 计算新的路径距离
            distance = d + weight
            # 如果新距离小于原始距离，则更新最短距离
            if distance < dist[neighbor]:
                dist[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
    return dist

2. Floyd算法：

def floyd(graph):
    dist = {}
    # 初始化距离矩阵
    for u in graph:
        dist[u] = {}
        for v in graph:
            dist[u][v] = graph[u].get(v, float('inf'))
    # 通过中间节点进行更新
    for k in graph:
        for i in graph:
            for j in graph:
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

3. Bellman-Ford算法：

def bellman_ford(graph, start):
    # 初始化距离矩阵和前驱节点列表
    dist = {v: float('inf') for v in graph}
    pred = {v: None for v in graph}
    dist[start] = 0
    # 进行n次松弛操作
    for _ in range(len(graph) - 1):
        for u in graph:
            for v, w in graph[u].items():
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    pred[v] = u
    # 检查是否存在负环
    for u in graph:
        for v, w in graph[u].items():
            if dist[u] + w < dist[v]:
                raise Exception('Graph contains negative-weight cycle')
    return dist

希望能够帮助你解决问题，如果还有其他问题，欢迎继续提问！