单源最短路径问题在图论中是一个经典问题，它涉及到在一个加权图中找到从单一源点到所有其他点的最短路径。以下是一些常见的方法来解决这类问题：

  • Dijkstra 算法：适用于图中所有边的权重都是非负数的情况。
  • Bellman-Ford 算法：可以处理图中包含负权边的情况。
  • Floyd-Warshall 算法：适用于稠密图，可以找到图中所有点对之间的最短路径。

示例代码

以下是一个使用 Python 和 Dijkstra 算法实现的单源最短路径问题的示例代码：

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        
        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(priority_queue, (distance, neighbor))
    
    return distances

# 示例图
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

# 计算从节点 'A' 到所有其他节点的最短路径
shortest_distances = dijkstra(graph, 'A')
print(shortest_distances)

扩展阅读

如果你对单源最短路径问题还有更多的疑问，可以参考以下链接：

图片展示

Dijkstra 算法示意图