最短路径算法python

在Python中，最常用的最短路径算法是Dijkstra算法和Bellman-Ford算法。

下面是Dijkstra算法的Python实现：

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    pq = [(0, start)]
    while pq:
        current_distance, current_vertex = heapq.heappop(pq)
        if current_distance > distances[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    return distances

其中，graph是一个字典，表示图的邻接表，start是起点。

你可以将你的图表示成邻接表的形式，然后调用dijkstra函数即可得到最短路径。

当然，如果你需要处理负权边，就要使用Bellman-Ford算法：

def bellman_ford(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor, weight in graph[vertex].items():
                if distances[vertex] + weight < distances[neighbor]:
                    distances[neighbor] = distances[vertex] + weight
    for vertex in graph:
        for neighbor, weight in graph[vertex].items():
            if distances[vertex] + weight < distances[neighbor]:
                raise ValueError("Negative weight cycle detected")
    return distances

同样，graph是邻接表，start是起点。Bellman-Ford算法的时间复杂度为O(VE)，其中V是顶点数，E是边数。