最短路径算法python

常见的最短路径算法有 Dijkstra 算法和 Floyd 算法。

Dijkstra 算法适用于有向无环图和有向图中没有负权边的情况，其思路是从起点开始不断扩展到未标记的节点，每次选取当前距离最短的节点作为标记节点，直到到达终点或者所有节点都被标记。

以下是 Dijkstra 算法的 Python 代码实现：

import heapq

def dijkstra(graph, start, end):
    # 初始化距离字典
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    # 初始化堆
    heap = [(0, start)]
    while heap:
        (d, node) = heapq.heappop(heap)
        # 如果当前节点已经被标记，则跳过
        if d > dist[node]:
            continue
        # 扩展当前节点的邻居节点
        for neighbor, weight in graph[node].items():
            new_dist = dist[node] + weight
            # 如果新的距离比原来的距离更短，则更新距离字典并加入堆
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    return dist[end]

Floyd 算法适用于有向图和有向图中可能存在负权边的情况，其思路是通过动态规划，依次尝试以每个节点为中转点来更新两个节点之间的最短路径。

以下是 Floyd 算法的 Python 代码实现：

def floyd(graph):
    # 初始化距离矩阵
    n = len(graph)
    dist = [[float('inf')]*n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
        for j, w in graph[i].items():
            dist[i][j] = w
    # 动态规划更新距离矩阵
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist