最短路径算法python

Python中实现最短路径算法有多种方法，以下是两个常用的算法：

1. Dijkstra算法

Dijkstra算法是一种贪心算法，用于解决有权图的单源最短路径问题。具体实现步骤如下：

（1）初始化：将起点s到所有点的距离都设为无穷大，s到s的距离为0。

（2）对于s的所有邻居节点，更新它们的距离。即若s到邻居节点的距离比之前计算的距离小，则更新邻居节点的距离。

（3）从未访问节点中选取最近的节点，将其加入已访问节点集合。

（4）重复步骤2和步骤3，直到所有节点都被访问过，或者目标节点被访问到。

Python代码如下：

import heapq

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

2. Bellman-Ford算法

Bellman-Ford算法是解决有权图的单源最短路径问题的一种算法，可以处理带有负权边的图。具体实现步骤如下：

（1）初始化：将起点s到所有点的距离都设为无穷大，s到s的距离为0。

（2）对于每条边(u, v)，如果从s到u的距离加上(u, v)的权值，小于从s到v的距离，则更新从s到v的距离。

（3）重复步骤2，直到所有边都被遍历V-1次，其中V为节点数。

Python代码如下：

def bellman_ford(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                distance = distances[node] + weight
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
    return distances

以上两个算法都可以实现最短路径的搜索，具体选择哪种算法取决于具体的需求和应用场景。