最短路径算法python

在Python中实现最短路径算法通常有两种方式：Dijkstra算法和Bellman-Ford算法。

Dijkstra算法实现：

import heapq

def dijkstra(graph, start):
    """
    :param graph: 图的邻接矩阵表示，graph[i][j]表示i到j的距离，如果不连通则为无穷大
    :param start: 起点
    :return: 返回一个列表，表示从起点到每个点的最短距离
    """
    n = len(graph)
    dist = [float('inf')] * n
    dist[start] = 0
    visited = set()
    pq = [(0, start)]  # 存储未访问的点，按照距离排序

    while pq:
        d, u = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
        for v in range(n):
            if graph[u][v] != float('inf'):
                if dist[v] > d + graph[u][v]:
                    dist[v] = d + graph[u][v]
                    heapq.heappush(pq, (dist[v], v))
    return dist

Bellman-Ford算法实现：

def bellman_ford(graph, start):
    """
    :param graph: 图的邻接矩阵表示，graph[i][j]表示i到j的距离，如果不连通则为无穷大
    :param start: 起点
    :return: 返回一个列表，表示从起点到每个点的最短距离
    """
    n = len(graph)
    dist = [float('inf')] * n
    dist[start] = 0

    for _ in range(n - 1):
        for u in range(n):
            for v in range(n):
                if graph[u][v] != float('inf'):
                    dist[v] = min(dist[v], dist[u] + graph[u][v])

    # 检查是否存在负环
    for u in range(n):
        for v in range(n):
            if graph[u][v] != float('inf') and dist[v] > dist[u] + graph[u][v]:
                raise ValueError("存在负环")

    return dist

以上两个算法的时间复杂度均为O(N^2)或O(ElogN)，其中N为节点数，E为边数。Dijkstra算法适用于稠密图，而Bellman-Ford算法适用于稀疏图和存在负边权的情况。