专栏首页Python七号一文搞懂戴克斯特拉算法-dijkstra

一文搞懂戴克斯特拉算法-dijkstra

大学学习数据结构那会,当时记得终于把 dijkstra 算法搞明白了,但是今天碰到的时候,大脑又是一片空白,于是我就又学习了下,把自己的理解写下来,希望你也可以通过本文搞懂 dijkstra 算法。

dijkstra 的起源

dijkstra 已经 62 岁了,是由荷兰计算机科学家艾兹赫尔·戴克斯特拉在 1956 年制造,并于 3 年后在期刊上发表,在 2001 年的采访中[1]他说到:从鹿特丹到格罗宁根的最短路径是什么?实际上,这就是对于任意两座城市之间的最短路问题。解决这个问题实际上大概只花了我 20 分钟:一天早上,我和我的未婚妻在阿姆斯特丹购物,累了,我们便坐在咖啡馆的露台上喝咖啡,然后我就试了一下能否用一个算法解决最短路问题。正如我所说,这是一个 20 分钟的发现。不过实际上,我在 3 年后的 1959 年才把这个算法发表在论文上。即使现在来看这篇论文的可读性也非常高,这个算法之所以如此优雅,其中一个原因就是我没用笔纸就设计了它。后来我才知道,没用笔纸设计的优点之一是你不得不避免所有可避免的复杂问题。令我惊讶的是,这个算法最终成为我成名的基石之一。"

dijkstra 解决什么问题

主要解决带权图的最短路径问题,如果图中的顶点表示城市,而边上的权重表示城市间开车行经的距离,该算法可以用来找到两个城市之间的最短路径。dijkstra 算法使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。

广度优先搜索,这个应该很形象,记得在算法实现的时候使用队列就可以了。赋权图也好理解,就是边上有权重值,可以理解为两点之间的距离,单源最短路径,就是一个已知的点到其他所有点的最短路径。

当然了,单源最短路径算法也不是只有 dijkstra,还有 Bellman-ford 算法或者 SPFA 算法,在边权非负时适合使用 Dijkstra 算法,若边权为负时则适合使用 Bellman-ford 算法或者 SPFA 算法。今天只聊 dijkstra。

dijkstra 算法思路

咱直接说优化后的思路,其实就是用到了小顶堆(优先级队列)来比较哪一个点的距离最近,关于堆排序,可以参考堆的实现及工程应用

从起点 s 开始,将与起点 s 直接相连的点,根据它与起点 s 的距离,加入到小顶堆中,堆顶那个点 s1 与起点 s 的距离 d1 一定是最近的,取出堆顶的点 s1 ,然后把与 s1 直接相连的点,根据它与 s 的距离(d1 + s1到这个点的距离),加入到小顶堆中,堆顶那个点 s2 与起点的距离就是最小的。

每次取出堆顶元素的时候,这个堆顶就是已确认的最近距离的点,把它加入已访问的集合中,防止无向图的重复计算,这样直到遍历完所有顶点,就找出了起点到所有点的最小距离。

是不是很简单,就是广度搜索,加上贪心的思想,先找出起点 s 开始直接相连的点(广度搜索),然后找出与 s 第一个最近的点(贪心),从最近的点出发,再次广度,再次贪心,就可以找出距离起点 s 第二个最近的点,直到全部搜索完毕。

算法时间复杂度 O(E+Vlog(v)) ,E 是边的数量,V 是定点的数量,Vlog(v) 其实就是堆排序的时间复杂度。

算法时间复杂度 O(E+V) 邻接矩阵的空间复杂度。

如果还不理解的话,多看几遍下这个动图:

dijkstra 代码实现(Python)

为了简化说明,我们使用邻接矩阵来表示一个图,图中有 n 个顶点,标记为 1,2,...n,现在要求解起点 1 到所有其他点的最小距离。

以终为始,先定义一个保存结果的最小距离的数组,cost[n] cost[i] 就是表示起点 1 到点 i+1 的最小距离,cost[0] = 0,起点 1 到它本身的距离是 0。这里 i+1 是因为数组下标从 0 开始。

假如有 6 个顶点,使用邻接矩阵来表示:

adjacency_matrix = [
    [0,  7,  9,  -1, -1, 14],
    [7,  0,  10, 15, -1, -1],
    [9,  10, 0,  11, -1,  2],
    [-1, 15, 11, 0,  6,  -1],
    [-1, -1, -1, 6,  0,   9],
    [14, -1,  2, -1,  9,   0]
]

adjacency_matrix[i][j] = c 意思就是点 i+1 到 j+1 的成本是 c,加一的原因是数组的下标从 0 开始。

下面是我根据上述思路,实现的 dijkstra 算法,里面有注释,不难看懂:

import sys
import heapq

max = sys.maxsize

vertices_number = 6
adjacency_matrix = [
    [0, 7, 9, -1, -1, 14],
    [7, 0, 10, 15, -1, -1],
    [9, 10, 0, 11, -1, 2],
    [-1, 15, 11, 0, 6, -1],
    [-1, -1, -1, 6, 0, 9],
    [14, -1, 2, -1, 9, 0],
]

cost = [max] * vertices_number
pq = []  # 优先级队列,最小堆


class Node(object):
    def __init__(self, vertex, distance):
        self.vertex = vertex
        self.distance = distance

    def __lt__(self, other):
        """
        为了进堆时比较大小,重写 __lt__ 方法
        """
        return self.distance < other.distance


def printpq(pq):
    ## debug 用,查看堆里面的数据
    for item in pq:
        print(item.vertex, item.distance, end="|")
    print("")


def dijkstra(from_vertex, dest_vertex):
    from_vertex = from_vertex - 1  # 转换为列表的下标,因此减 1
    dest_vertex = dest_vertex - 1
    visited = set()  # 定义已经确定最小距离的点,防止重复计算。

    # 起点入队
    heapq.heappush(pq, Node(from_vertex, 0))  # 按照距离比较大小进堆
    while pq and len(visited) < vertices_number:
        # printpq(pq)
        # 出队
        node = heapq.heappop(pq)
        from_vertex1 = node.vertex
        distance1 = node.distance
        if from_vertex1 in visited:
            # 如果改点已经确认了最小距离,直接抛弃。
            continue
        # 更新距离,已经确定时最小距离的点加入已访问集合。
        print(from_vertex1)
        cost[from_vertex1] = distance1
        visited.add(from_vertex1)
        # 取出 from_vertex1 的邻居节点,
        for index, distance in enumerate(adjacency_matrix[from_vertex1]):
            # 只选择与 from_vertex1 连通的点,也就是邻居,排除已经确定了最小值的点。
            if distance > 0 and index not in visited:
                heapq.heappush(pq, Node(index, distance + distance1))

    return -1 if cost[dest_vertex] == max else cost[dest_vertex]


if __name__ == "__main__":
    print(dijkstra(1, 5))
    #其他点的最小距离均已经计算得出:
    print(cost)
    # assert 20 == dijkstra(1, 5)

最后的话

纯粹的记忆算法的实现其实没有太大用处,算法最重要的是理解它的思路,以及学会灵活的运用,比如说从 A 到 B 中间最多经过 k 个节点的最小距离,你可以试着用 dijkstra 算法的思路来求解么?假如有负数的权值,怎么用 dijkstra 算法求解?

如果有问题,请留言赐教

都看到这里了,你不确定不关注一下吗?😄

参考资料

[1]

在 2001 年的采访中: https://zh.wikipedia.org/wiki/%E6%88%B4%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95

本文分享自微信公众号 - Python七号(PythonSeven),作者:somenzz

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-08-25

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【算法】Dijkstra 算法:解决单源最短路径问题

    Dijkstra算法,中文名音译作迪杰斯特拉算法或戴克斯特拉算法,它是一个用来解决赋权图的单源最短路径问题的算法。

    叶锦鲤
  • 最短路径—弄懂Dijkstra(迪杰斯特拉)算法

    对于 dijkstra算法,很多人可能感觉熟悉而又陌生,可能大部分人比较了解 bfs和dfs,而对dijkstra和floyd算法可能知道大概是图论中的某个算法...

    bigsai
  • 【你该懂一点Javascript算法系列】之单源最短路径 - Dijkstra算法

    ps: 邻接矩阵的意思是: 用一个二数组表示个顶点间的关系,来确定各顶点间的关系,因为图为有向图,所以上图的邻接矩阵如上

    super.x
  • [图]最短路径-Dijkstra算法

    2.BFS可能会是Dijkstra算法的实质,BFS使用的是队列进行操作,而Dijkstra采用的是优先队列。

    王荣胜
  • dijkstra算法原理是什么?dijkstra算法的缺点是什么?

    dijkstra算法也被称为狄克斯特拉算法,是由一个名为狄克斯特拉的荷兰科学家提出的,这种算法是计算从一个顶点到其他各个顶点的最短路径,虽然看上去很抽象,但是在...

    用户8739990
  • SPF单源最短路径算法

    SPF(shortest path first)算法也叫Dijkstra(迪杰斯特拉)算法,由上个世纪的计算机科学家狄克斯特拉提出,是离散数学中一种经典高效的网...

    Jean
  • 《算法图解》note 7 狄克斯特拉算法1.狄克斯特拉算法简介2.代码实例

    billyang916
  • 一步一步深入理解Dijkstra算法

    先简单介绍一下最短路径: 最短路径是啥?就是一个带边值的图中从某一个顶点到另外一个顶点的最短路径。 官方定义:对于内网图而言,最短路径是指两顶点之间经过的边...

    Angel_Kitty
  • 我心目中的编程高手

    -- Bill Joy MIT BBS上说微软电话面试的一道题就是“Who do you think is the best coder, and why?”。...

    程序员互动联盟
  • 读完这7本算法书,你也可以像这10位算法大师一样改变世界

    导读:算法是整个计算机科学的基石,是计算机处理信息的本质。从开创算法分析这一领域的高德纳、Amazon的“首席算法官”乌迪·曼伯尔,到发明快速排序算法托尼·霍尔...

    华章科技
  • 算法与数据结构algorithm

    算法与数据结构 《Data structures》 介绍:高级数据结构大全,基本算法:二叉树等 《基于用户投票的排名算法(一):Delicious和Hacker...

    Albert陈凯
  • 硅谷快意恩仇录:战斗力爆表的10对科技公司CEO之争

    硅谷是科技公司的天堂,吸引最有创造力的人来此实现自己的想法。这里孕育着看似千奇百怪,但最终成为科技前沿的互联网技术。

    新智元
  • 最短路径问题--迪杰斯特拉(Dijkstra)算法

    迪杰斯特拉(Dijkstra)算法是典型的用来解决最短路径的算法,也是很多教程中的范例,由荷兰计算机科学家狄克斯特拉于1959年提出,用来求从起始点到其他所有点...

    用户6021899
  • 【干货】十大必须掌握的基础实用算法及其讲解

    快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较,但这种状况并不常见。...

    钱塘数据
  • 程序员必须知道的十大基础实用算法及其讲解

    算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较...

    CSDN技术头条
  • 用少终端解决斯坦纳树问题(CS AI)

    斯坦纳树问题是网络设计、路由和超大规模集成电路设计中众所周知的问题。给定一个图、边成本和一组专用顶点(终端),斯坦纳树问题要求输出一个以最小成本连接所有终端的子...

    识檐
  • 程序员必须知道的十大基础实用算法及其讲解

    快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较,但这种状况并不常见。...

    华章科技
  • 人工智能深度学习人物关系[全]

    为庆祝祖国母亲生日和自己终于脱单,给大家献上这篇绝对的干货!也提前祝大家国庆快乐!

    史博
  • Python语言实现Dijkstra算法

    Dijkstra算法是由荷兰计算机科学家狄克斯特拉(Dijkstra)于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决...

    week

扫码关注云+社区

领取腾讯云代金券