Dijkstra最短路径算法

  • 示例
  • 伪代码
  • 分析

Dijkstra算法是目前比较主流的计算最短路径的方法,求取一个顶点到其余各顶点的最短路径,也称作单源最短路径。它的主要特点是从起始点开始,采用贪心的策略对点进行遍历,层层遍历(广度优先搜索思想)。

示例

伪代码

def Dijkstra(graph, start):
    # 初始化
    X = set() # 记录遍历过的节点
    X.add(start)
    A = dict() # 记录起始点start到每个节点的距离
    A[start] = 0
    B = dict() # 记录起始点start到每个节点的路径
    B[start] = [s]

    # 算法部分
    while X != V: # 确保处理了图中的每一个点
        # 找到图中的边(v, w),其中v在X中(即被处理过)而w不在
        vs = [] # v
        ws = [] # w
        ls = [] # 边的长度l
        for v in X:
            for w, l in graph[v].items():
                if w not in A:
                    vs.append(v)
                    ws.append(w)
                    ls.append(A[v] + l)
        # 找到A[v]+l的最小值,将对应的w加入到X中
        X.add(w_star)
        # 距离加入到A中
        A[w_star] = min(ls)
        # 路径加入到B中
        B[w_star] = B[v_star] + [w_star]
    return A, B
        

Python实现代码:https://github.com/xueqiwang0v0/Dijkstra

在这个代码实现里没有加入路径,只单纯计算了路径长度。

分析

  • 时间复杂度

假设一个图有n个节点,m条边,那么上述方法的时间复杂度为\Theta(mn)。在while loop中有n-1次迭代,每次迭代时间复杂度为\Theta(m)

  • 简化

如果图非常复杂,就需要进一步简化算法。采用堆(Heap)就是其中一种方法。将X和V-X的存储改用堆,会减少冗余的遍历情况。时间复杂度为\Theta(m\log n)

  • 局限

需要注意的是,Dijkstra算法只能处理边长为非负的图。有下面几种情况可以思考:

  1. 只有一条边长度为负,其余边均为非负:可以找到最短路径。
  2. 有多条边长度为负,但不存在负的环路:可能找到最短路径,也可能找不到。
  3. 存在负的环路:找不到最短路径。

负的环路即为这个环路的边之和为负。

无论能否找到最短路径,程序在遍历完所有的节点之后都会停止。

参考资料

  1. 百度 迪克斯特拉算法
  2. Stanford算法课 Graph Search, Shortest Paths, and Data Structures_week2

You May Also Like

About the Author: 雪球

一个在读的工科研究生 一个努力追赶时代脚步的人 Github: https://github.com/xueqiwang0v0 LinkedIn: https://www.linkedin.com/in/xueqi-wang-0939b51a6/

发表评论

邮箱地址不会被公开。 必填项已用*标注