写一个图论最短距离的代码
时间: 2023-12-01 17:11:12 浏览: 40
以下是使用Dijkstra算法求解最短路径的Python代码示例,假设图中有n个节点,节点编号从0到n-1,节点之间的距离存储在一个n*n的邻接矩阵adj中,如果节点i和节点j之间没有边相连,则adj[i][j]为无穷大(可以使用一个较大的数表示,比如999999):
```python
import heapq
def dijkstra(adj, start):
n = len(adj)
dist = [float('inf')] * n # 到各个节点的距离
dist[start] = 0
visited = [False] * n # 是否访问过
pq = [(0, start)] # 优先队列,存储节点及到起点的距离
while pq:
d, u = heapq.heappop(pq)
if visited[u]:
continue
visited[u] = True
for v in range(n):
if adj[u][v] < float('inf') and not visited[v]:
if dist[u] + adj[u][v] < dist[v]:
dist[v] = dist[u] + adj[u][v]
heapq.heappush(pq, (dist[v], v))
return dist
```
该代码中使用一个优先队列(Python中使用heapq实现)存储节点及到起点的距离,每次从队列中取出距离最短的节点进行松弛操作。在松弛操作中,对于每个相邻节点v,如果从起点到u再到v的距离比已知的从起点到v的距离更短,则更新v的距离,并将其加入队列中等待处理。最终,返回一个数组dist,表示从起点到各个节点的最短距离。