Dijkstra 算法
Dijkstra 解决的是图上的单源最短路径问题(Single Source Shortest Path,SSSP)。
实现大致代码如下:
def dijkstra(graph, source):
Q = priority_queue()
# initialize dist and Q
dist[source] = 0
for v in graph.vertices:
if v != source:
dist[v] = INF
Q.add_with_priority(v, dist[v])
while not Q.empty:
# find min dist and relax edge
u = Q.extract_min()
for v in u.neighbors():
# relax
new_dist = dist[u] + u.dist_to(v)
if new_dist < dist[v]:
dist[v] = new_dist
Q.decrease_priority(v, new_dist)
Q 是一个优先队列,队列每个元素都有优先级,支持如下操作:
add_with_priority(element, priority)
:插入新元素empty()
:判断队列是否为空extract_min()
:从队列中删除优先级最低的元素并返回该元素decrease_priority()
:修改队列中特定元素的优先级,保证队列中没有重复元素
算法的时间复杂度是 decrease_priority()
的时间复杂度,extract_min()
的时间复杂度。
根据优先队列的不同实现,得到不同的时间复杂度:
- 用数组实现优先队列,则
,因此时间复杂度是 - 用平衡树或者堆(需要额外记录每个顶点在堆中的位置,随着堆的更新而更新)实现优先队列,则
,算法总时间复杂度为 - 用 Fibonacci 堆实现优先队列,则
,算法总时间复杂度为
最近一篇论文 A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs 提出了
参考了 Wikipedia。