给定一个带权有向图G= (V,E),其中每条边的权是一个实数。另外,还给定V中的一个顶点,称为源。现在要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。请写出代码
时间: 2024-02-17 18:04:44 浏览: 293
这个问题可以使用 Dijkstra 算法解决。以下是 Python 代码实现:
```python
import heapq
def dijkstra(graph, start):
# 初始化距离字典和最小堆
dist = {vertex: float('inf') for vertex in graph}
dist[start] = 0
heap = [(0, start)]
while heap:
# 弹出当前最小距离的顶点
current_dist, current_vertex = heapq.heappop(heap)
# 如果当前距离已经大于已知最小距离,则跳过
if current_dist > dist[current_vertex]:
continue
# 更新相邻顶点的距离
for neighbor, weight in graph[current_vertex].items():
distance = current_dist + weight
if distance < dist[neighbor]:
dist[neighbor] = distance
heapq.heappush(heap, (distance, neighbor))
return dist
```
其中,`graph` 是图的邻接表表示,`start` 是源顶点。返回值是一个字典,记录了从源顶点到各个顶点的最短路径长度。
阅读全文