数据结构(十二):最短路径(Dijkstra算法)

通过上一章最短路径(Bellman-Ford算法)的内容可知,Bellman-Ford 算法是通过重复对边集执行松弛函数,来逐渐获得从起点到各个顶点的最短路径。并且对边的松弛顺序是随意进行的,所以才有最好情况和最坏情况之分。一般情况下则是通过不断的对边集进行重复松弛,来“堆”出从起点到其他顶点的最短路径,这种“盲目”的松弛存在极多的无效操作和时间浪费。

Dijkstra 算法使用贪心策略计算从起点到指定顶点的最短路径,通过不断选择距离起点最近的顶点,来逐渐扩大最短路径权值,直到覆盖图中所有顶点。

Dijkstra 算法前提为图中边的权值非负,若将最短路径中经过的顶点个数称为最短路径长度,则最短路径长度与最短路径权值呈正相关。而在 Bellman-Ford 算法中,因为边的权值可能为负,所以最短路径长度较大的顶点,其最短路径权值不一定更大。所以与 Bellman-Ford 算法相似,Dijkstra 算法的计算最短路径过程,也是呈现一种波纹扩散的方式,不同之处在于,Bellman-Ford 算法扩散过程中,逐渐增大的半径为最短路径长度,而 Dijkstra 算法的扩大半径为最短路径权值。

Dijkstra 算法过程中也存在对边的松弛行为,不过该松弛过程并非“盲目”的对所有边进行松弛,而是对于已确认顶点为出度,未确认顶点为入度的边进行松弛。因为 Dijkstra 算法过程中每个顶点被确认一次,所以整个算法过程只需要对边集执行一次松弛,即边的松弛复杂度为

算法过程

  1. 从未确认顶点中选择距离起点最近的顶点,并标记为已确认顶点
  2. 根据步骤 1 中的已确认顶点,更新其相邻未确认顶点的距离
  3. 重复步骤 1,2,直到不存在未确认顶点

演示示例

graph

以图 graph 为例,边的权值如图中所示,初始化各顶点距离起点权值为 None,不妨随机选择一个顶点作为起点,初始化起点的权值为 0

选择距离起点最近的顶点为已确认顶点,并更新该顶点的相邻未确认顶点距离

step 1:

第一次选择最近的顶点为起点自身,并更新相邻未确认顶点的距离

step 2:

step 3:

step 4:

step 5:

step 6:

step 7:

step 8:

step 9:

算法示例

  1. Dijkstra 算法示例
def dijkstra(graph, start):
    vertices, verticesIndex = [{'index': i, 'weight': None} for i in range(graph.number)], [i for i in range(graph.number)]
    vertices[start - 1]['weight'] = 0
    heapSort(vertices, verticesIndex)
    while len(vertices) > 0:
        swapVertices(vertices, verticesIndex, 0, -1)
        vertex = vertices.pop()
        transformToHeap(vertices, verticesIndex, 0, len(vertices))
        updateDistance(graph, vertices, verticesIndex, vertex)

这里使用 vertices 列表存储每个顶点元素,每个元素包括两个属性,index 为顶点下标,weight 为顶点距离起点的大小。算法中使用 verticesIndex 列表存储每个顶点元素在 vertices 列表中的下标位置。使用 heapSort 堆排序对每个顶点到起点的距离进行排序,即对 vertices 列表进行排序。使用 swapVertices 函数将 vertices 列表首尾元素交换,将最小元素放置在列表尾部并执行出栈操作,使用 transformToHeap 函数调整 vertices 列表为小顶堆,然后调用 updateDistance 函数完成对相邻顶点的距离更新。

  1. 交换列表首尾元素
def swapVertices(vertices, verticesIndex, origin, target):
    vertices[origin], vertices[target] = vertices[target], vertices[origin]
    verticesIndex[vertices[origin]['index']], verticesIndex[vertices[target]['index']] = origin, target

vertices 列表调整为小顶堆之后,将列表首、尾元素交换,则列表尾元素即为距离起点最近的顶点元素。

  1. 将列表尾部顶点元素出栈后,更新该顶点的相邻未确认顶点距离起点的权值
def updateDistance(graph, vertices, verticesIndex, agent):
    node = graph.list[agent['index']]
    while node:
        if verticesIndex[node.index - 1] == -1:  # whether the node in sub graph
            node = node.next
            continue
        vertex = vertices[verticesIndex[node.index - 1]]
        if not vertex['weight'] or vertex['weight'] > agent['weight'] + node.weight:
            vertex['weight'] = agent['weight'] + node.weight
            pos = verticesIndex[vertex['index']]
            while pos > 0 and (not vertices[(pos - 1) // 2]['weight'] or vertices[pos]['weight'] < vertices[(pos - 1) // 2]['weight']):
                swapVertices(vertices, verticesIndex, pos, (pos - 1) // 2)
                pos = (pos - 1) // 2
        node = node.next

对每一个相邻顶点,若属于未确认顶点,则判断是否更新到起点的距离。更新距离后的 while 循环操作,目的为调整堆结构为小顶堆。

Dijkstra 算法及算法中调用的函数都与 prim 算法较大相像,可以参考最小生成树prim 算法的部分作辅助理解。

性能分析

dijkstra 算法中构造顶点列表的时间复杂度为

。使用堆排序对顶点列表进行排序,时间复杂度为

dijkstra 算法中 while 循环取权值最小顶点元素,并调整元素取出后列表的堆结构,所以调整复杂度为

;同时,循环结构内执行 updateDistance 函数,更新每个取出顶点的相邻顶点权值,所以更新顶点数为

,因为每个顶点更新距离后,需要调整堆结构为小顶堆,所以更新复杂度为

。所以prim 算法的总时间复杂度为

代码及测试 github 链接:最短路径(Dijkstra算法)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏温安适的blog

最小生产树Prim和Kruskal

483120
来自专栏数据结构与算法

1038 一元三次方程求解

1038 一元三次方程求解 2001年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver ...

29880
来自专栏数据结构与算法

洛谷P2678 跳石头

题目背景 一年一度的“跳石头”比赛又要开始了! 题目描述 这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终...

35050
来自专栏程序生活

Leetcode-Easy 70. Climbing Stairs

21. Merge Two Sorted Lists 描述: 有n阶楼梯,每步只能走1个或2个台阶,请问到达第n阶楼梯一共有多少走法? ? ...

33160
来自专栏算法修养

FZU 2087 统计树边

Problem 2087 统计树边 Accept: 197 Submit: 571 Time Limit: 1000 mSec Memory...

356110
来自专栏编程理解

数据结构(七):图

图是由若干给定的顶点及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物,连接两顶点的边则用于表示两个事物间具有这种关...

12930
来自专栏WD学习记录

Python数据结构与算法笔记(5)

邻接矩阵优点是简单,对于小图,很容易看到哪些节点连接到其他节点。但是大多数单元格是空的,即稀疏。

14730
来自专栏移动开发面面观

OpenGL ES——导入.stl格式的3D模型

22640
来自专栏bboysoul

1067: 成绩评估

描述:我们知道,高中会考是按等级来的。90~100为A; 80~89为B; 70~79为C; 60~69为D; 0~59为E。 编写一个程序,对输入的...

9520
来自专栏Phoenix的Android之旅

一张图看懂开发和运营的思维差别

用Dijkstra算法很简单,我们需要 · 用 6*6矩阵 source[6][6]表示点之间的距离,也就是图中的权值 · 自己与自己的距离为0,无直接连接的距...

8510

扫码关注云+社区

领取腾讯云代金券