Dijkstra方法的代码实现
时间: 2024-02-22 13:57:53 浏览: 17
以下是Dijkstra算法的Python代码实现,假设有一个加权无向图,以邻接矩阵的形式存储,其中inf表示两个节点之间没有边相连:
```python
import sys
def dijkstra(graph, start):
# 初始化距离列表和visited列表
dist = [sys.maxsize] * len(graph)
visited = [False] * len(graph)
# 起点到起点的距离为0
dist[start] = 0
# 遍历每个节点
for i in range(len(graph)):
# 选择一个距离最小的节点
min_dist = sys.maxsize
min_node = -1
for j in range(len(graph)):
if not visited[j] and dist[j] < min_dist:
min_dist = dist[j]
min_node = j
# 标记该节点已访问
visited[min_node] = True
# 更新与该节点相邻的节点的距离
for k in range(len(graph)):
if graph[min_node][k] != sys.maxsize and not visited[k]:
new_dist = dist[min_node] + graph[min_node][k]
if new_dist < dist[k]:
dist[k] = new_dist
return dist
```
该算法的时间复杂度为O(n^2),其中n为节点数。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)