Dijkstra 算法 实现
时间: 2023-11-10 20:45:20 浏览: 34
Dijkstra 算法是用于计算单源最短路径的算法。它的基本思想是,从起点开始,每次找到距离起点最近的未曾经访问过的顶点,并更新它到起点的最短路径。
算法步骤如下:
1. 将起点加入已访问的顶点集合,并将其到起点的距离设为 0。
2. 从起点开始,每次找到距离起点最近的未曾经访问过的顶点 u。
3. 将 u 加入已访问的顶点集合,并更新从起点到所有顶点 v 的距离,如果从起点到 u 再到 v 的距离比目前记录的距离更小,就更新它。
4. 重复步骤 2 和 3,直到所有的顶点都被访问过。
Dijkstra 算法的时间复杂度为 O(n^2),如果使用堆优化,则可以将时间复杂度优化到 O(nlogn)。
相关问题
dijkstra算法实现
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为节点数。
Dijkstra 算法实现案例
好的,以下是一个使用 Dijkstra 算法实现最短路径查找的 Python 代码示例:
```python
import heapq
def dijkstra(graph, start, end):
# 初始化距离字典
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
# 初始化堆和访问过的集合
pq = [(0, start)]
visited = set()
while pq:
# 取出距离最小的顶点
(current_distance, current_vertex) = heapq.heappop(pq)
# 如果已经访问过,则跳过
if current_vertex in visited:
continue
# 将当前顶点标记为已访问
visited.add(current_vertex)
# 如果已经到达终点,则直接返回最短路径距离
if current_vertex == end:
return distances[end]
# 遍历当前顶点的所有邻居
for neighbor, weight in graph[current_vertex].items():
# 计算新的距离
distance = current_distance + weight
# 如果新距离更短,则更新距离字典和堆
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
# 如果无法到达终点,则返回 None
return None
```
这个函数接受一个邻接字典 `graph`,表示图中每个顶点的邻居和权重;起点 `start` 和终点 `end`。它使用堆和距离字典来实现 Dijkstra 算法,最后返回起点到终点的最短路径距离,如果无法到达终点则返回 None。