狄克斯特拉算法求起一点到其余各点的最短路径代码
时间: 2023-06-17 16:06:43 浏览: 46
以下是使用Python实现Dijkstra算法的代码,假设图以邻接矩阵的形式表示,其中inf表示两点之间没有边相连:
```python
import sys
def dijkstra(graph, start):
n = len(graph)
dist = [sys.maxsize] * n
visited = [False] * n
dist[start] = 0
for _ in range(n):
# 找到当前未访问的最短距离的节点
min_dist = sys.maxsize
min_index = -1
for i in range(n):
if not visited[i] and dist[i] < min_dist:
min_dist = dist[i]
min_index = i
# 标记当前节点为已访问
visited[min_index] = True
# 更新所有与当前节点相邻的节点的最短距离
for j in range(n):
if not visited[j] and graph[min_index][j] != sys.maxsize:
new_dist = dist[min_index] + graph[min_index][j]
if new_dist < dist[j]:
dist[j] = new_dist
return dist
```
其中graph是邻接矩阵,start是起点。函数返回一个列表dist,表示起点到所有其他节点的最短距离。