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()：修改队列中特定元素的优先级，保证队列中没有重复元素

算法的时间复杂度是 $O (| E | T_{d p} + | V | T_{e m})$ ，其中 $E$ 是边的集合， $V$ 是顶点的集合， $T_{d p}$ 是 decrease_priority() 的时间复杂度， $T_{e m}$ 是 extract_min() 的时间复杂度。

根据优先队列的不同实现，得到不同的时间复杂度：

用数组实现优先队列，则 $T_{d p} = O (1), T_{e m} = O (| V |)$ ，因此时间复杂度是 $O (| E | + | V |^{2}) = O (| V |^{2})$
用平衡树或者堆（需要额外记录每个顶点在堆中的位置，随着堆的更新而更新）实现优先队列，则 $T_{d p} = O (\log | V |), T_{e m} = O (\log | V |)$ ，算法总时间复杂度为 $O ((| E | + | V |) \log | V |)$
用 Fibonacci 堆实现优先队列，则 $T_{d p} = O (1), T_{e m} = O (\log | V |)$ ，算法总时间复杂度为 $O (| E | + | V | \log | V |)$

最近一篇论文 A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs 提出了 $O (| E | \sqrt{\log | V | \log \log | V |})$ 的 Dijkstra 变种算法。

参考了 Wikipedia。

Dijkstra 算法

Comments