dijkstra算法实现
时间: 2023-09-24 22:09:51 浏览: 48
Dijkstra算法是一种经典的单源最短路径算法,它的基本思路是从源点开始,逐步扩展到其他节点,每次找到距离源点最近的节点,并更新与该节点相邻的节点的距离。以下是一种Dijkstra算法的实现:
1. 初始化距离数组dist,将源点的距离设为0,其它节点的距离设为无穷大。
2. 初始化节点集合S,将源点加入集合S中。
3. 对于源点的所有邻居节点,更新它们的距离,即如果从源点到该邻居节点的距离小于当前距离,则更新距离数组dist。
4. 从节点集合S中选取距离源点最近的节点v,并将该节点从集合S中移除。
5. 对于节点v的所有邻居节点,如果该邻居节点不在集合S中,则将该邻居节点加入集合S,并更新它们的距离。
6. 重复步骤4-5,直到集合S为空。
以下是一个Python实现:
```
import heapq
def dijkstra(graph, start):
dist = [float('inf')] * len(graph)
dist[start] = 0
visited = set()
pq = [(0, start)]
while pq:
(d, v) = heapq.heappop(pq)
if v in visited:
continue
visited.add(v)
for neighbor, weight in graph[v].items():
if dist[v] + weight < dist[neighbor]:
dist[neighbor] = dist[v] + weight
heapq.heappush(pq, (dist[neighbor], neighbor))
return dist
```
其中graph是一个邻接表,表示图的结构和权重,start是源点的编号。函数返回一个距离数组dist,表示从源点到各个节点的最短距离。该算法的时间复杂度为O(ElogV),其中E为边数,V为节点数。
相关推荐
![](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)
![](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)
![](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)
![](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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)