python最短路径算法

Python中有很多种最短路径算法，以下是其中几种：

1. Dijkstra算法

Dijkstra算法是一种贪心算法，用于找到从单个源节点到所有其他节点的最短路径。

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heap = [(0, start)]
    while heap:
        (distance, current_node) = heapq.heappop(heap)
        if distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance_to_neighbor = distance + weight
            if distance_to_neighbor < distances[neighbor]:
                distances[neighbor] = distance_to_neighbor
                heapq.heappush(heap, (distance_to_neighbor, neighbor))
    return distances

2. Bellman-Ford算法

Bellman-Ford算法是一种动态规划算法，用于解决带有负权边的最短路径问题。

def bellman_ford(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if distances[node] + weight < distances[neighbor]:
                    distances[neighbor] = distances[node] + weight

    for node in graph:
        for neighbor, weight in graph[node].items():
            if distances[node] + weight < distances[neighbor]:
                raise ValueError("Negative weight cycle detected")

    return distances

3. Floyd-Warshall算法

Floyd-Warshall算法是一种动态规划算法，用于找到所有节点对之间的最短路径。

def floyd_warshall(graph):
    distances = graph
    for k in range(len(graph)):
        for i in range(len(graph)):
            for j in range(len(graph)):
                distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])
    return distances

以上是几种常用的最短路径算法，选择哪种算法取决于问题的具体情况。