精华内容
下载资源
问答
  • 戴克斯特拉算法(英语:Dijkstra'salgorithm),又译迪杰斯特拉算法,亦可不音译而称为Dijkstra算法,是由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年发现的算法,并于3年后在期刊上发表。戴克斯特拉算法使用类似...

    简介

    狄克斯特拉算法解决了**有向图最短路径**的问题。

    戴克斯特拉算法(英语:Dijkstra'salgorithm),又译迪杰斯特拉算法,亦可不音译而称为Dijkstra算法,是由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年发现的算法,并于3年后在期刊上发表。戴克斯特拉算法使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。

    基本思路

    狄克斯特拉算法包含4个步骤。

    (1) 找出“最便宜”的节点,即可在最短时间内到达的节点。

    (2) 更新该节点的邻居的开销。

    (3) 重复这个过程,直到对图中的每个节点都这样做了。

    (4) 计算最终路径。

    图解算法

    78a7f2a28c39635349b5e97a5f36e1a1.png

    上图中包括6个节点,箭头表示方向,线上的数字表示耗费时间。比如从start到B节点需要花费2个时间单位。但是从B却无法到达Start,因为箭头是有方向的。

    首先根据上图做出一个初始表(父节点代表从哪个节点到达该节点):

    19008dd435458e7853f3471cafc7d226.png

    然后从start开始,根据图中的信息更新一下表,由于从start不能直接到达C和End节点,所以耗时为∞(无穷大),从start到B花费2,从start到A花费6:

    4170ab24e502465e06b66375ceb4e5b4.png

    有了这个表我们可以根据算法的步骤往下进行了。

    第一步:找出“最便宜”的节点,这里是节点B(只花费了2):

    d36ae73a99d32f1a116c7927128eb9b6.png

    第二步:更新该节点的邻居的开销,根据图从B出发可以到达C和End节点,B目前的消耗2+B到C的消耗1=3(因为要从start开始算花费,所以要把从start到B的花费加上),3小于原来C的消耗∞,所以更新节点C相关的行:

    d0631c90c0dd864603c389f568fc5030.png

    同理,B目前消耗2+B到End的消耗7=9,小于∞,更新End节点行:

    05f5eb64599d96296268830fe793daea.png

    B节点关联的节点已经更新完成,所以B节点不在后面的更新范围之内了:

    3ee971039181ae399a2166a985b1628b.png

    找到下一个消耗最小的节点,那就是C节点:

    f5e1c124f8f8422f3e3a04a190330688.png

    根据C节点的消耗更新关联节点,只有End节点行被更新了,C目前的消耗3+C到end的消耗5=8:

    a79928ab383faa64aa7e6e43e7e9ea3e.png

    这时候C节点也不在更新节点范围之内了,把C节点置灰:

    7093f9de6144dc37c013c94f098ac141.png

    最后只剩下A节点了,根据A节点的消耗没有更新任何行,A节点只能到达End节点,A节点目前的消耗6+A节点到End节点的消耗4=10,由于10大于8所以End节点行不更新:

    df6471b733492237eb6eb949bd336ff0.png

    最终表的数据如下:

    e1eb3187cf405d35a39fb93ac0b9e742.png

    根据最终表,从Start到End的最少消耗是8,路径是Start->B->C->End.这个路径是从后往前推出来的,End<-C<-B<-Start.

    代码实现

    graph = {}
    graph["Start"] = {}
    graph["Start"]["A"] = 6
    graph["Start"]["B"] = 2
    graph["A"] = {}
    graph["A"]["End"] = 4
    graph["B"] = {}
    graph["B"]["C"] = 1
    graph["B"]["End"] = 7
    graph["C"] = {}
    graph["C"]["A"] = 4
    graph["C"]["End"] = 5
    
    infinity = float("inf")
    costs = {}
    costs["A"] = 6
    costs["B"] = 2
    costs["C"] = infinity
    costs["End"] = infinity
    
    parents = {}
    parents["A"] = "Start"
    parents["B"] = "Start"
    parents["C"] = None
    parents["End"] = None
    
    
    def findLowestCostNode(costs, processed):
        lowest_cost = infinity
        lowest_cost_node = None
        for node in costs:
            cost = costs[node]
            if cost < lowest_cost and node not in processed:
                lowest_cost = cost
                lowest_cost_node = node
    
        return lowest_cost_node
    
    
    def Dijkstra():
        processed = []
        node = findLowestCostNode(costs, processed)
        while node is not None and node != "End":
            cost = costs[node]
            neighbors = graph[node]
            for n in neighbors.keys():
                new_cost = cost + neighbors[n]
                if new_cost < costs[n]:
                    costs[n] = new_cost
                    parents[n] = node
    
            processed.append(node)
            node = findLowestCostNode(costs, processed)
    
    
    Dijkstra()
    print(costs)
    print(parents)

    实际生活中的使用例子

    • 地图

    如果您曾经尝试查找从一个点/位置到另一点/目的地的距离或路径,或者说从一个城市到另一个城市,或者从您的位置到最近的加油站,这很可能是您遇到的最短路径问题。 用数学术语来说,它是在图中两点之间找到最短的路径,Dijkstra的算法很可能适用于此。

    另一个示例是消防员部门想要开发一种系统,该系统可以找到距离最近的消防员部门与被烧房屋之间的最短距离,以避免额外的延迟。 或者,物流公司希望开发一种系统,该系统可以找到仓库和目的地之间最短的距离,以避免额外的花费和时间。 对于此类系统的开发,Dijkstra的算法非常适用。

    • 社交网络应用

    在许多社交网络应用程序中,推送给特定用户的可能认识的朋友列表非常普遍。您如何看待许多社交媒体公司如何有效地实现此功能,特别是当系统拥有十亿用户时。可以使用握手或两个用户之间的连接度,利用Dijkstra算法计算出来。

    许多社交网络应用程序都基于六个分离度,这是用两个用户之间的握手次数来衡量的距离。即使用户的平均朋友数量不大,从算法复杂性的角度来看,找到用户之间最短路径的问题也非常复杂。

    • 电话网

    在电话网络中,每条线都有带宽bw。 我们想将电话路由到最高带宽。传输线的带宽是该线路可以支持的最高频率。 通常,如果在某条线路中信号的频率较高,则该线路会降低信号的频率。带宽表示线路可以传输的信息量。

    如果我们将一个城市想象成一个图形,则顶点代表交换站,边代表传输线,边的权重代表bw。 因此,它可以归为最短距离问题,Dijkstra非常适用。

    展开全文
  • 前言在图论中,在寻路最短路径中除了Dijkstra算法以外,还有Floyd算法也是非常经典,然而两种算法还是有区别的,Floyd主要计算多源最短路径。在单源正权值最短路径,我们会用Dijkstra算法来求最短路径,并且算法的...

    前言

    746cdfe35ff0a3b1253780d0bfad74d5.png

    图论中,在寻路最短路径中除了Dijkstra算法以外,还有Floyd算法也是非常经典,然而两种算法还是有区别的,Floyd主要计算多源最短路径。

    在单源正权值最短路径,我们会用Dijkstra算法来求最短路径,并且算法的思想很简单——贪心算法:每次确定最短路径的一个点然后维护(更新)这个点周围点的距离加入预选队列,等待下一次的抛出确定。但是虽然思想很简单,实现起来是非常复杂的,我们需要邻接矩阵(表)储存长度,需要优先队列(或者每次都比较)维护一个预选点的集合。还要用一个boolean数组标记是否已经确定、还要---------

    总之,Dijkstra算法的思想上是很容易接受的,但是实现上其实是非常麻烦的。但是单源最短路径没有更好的办法。复杂度也为O(n2)

    而在n节点多源最短路径中,如果从Dijkstra算法的角度上,只需要将Dijkstra封装,然后执行n次Dijkstra算法即可,复杂度为O(n3)。但是这样感觉很臃肿,代码量巨大,占用很多空间内存。有没有啥方法能够稍微变变口味呢?

    答案是有的,这就是易写但稍需要理解的Floyd算法。一个求多元最短路径算法。

    算法介绍

    先看看百度百科的定义吧:

    Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

    简单的来说,算法的主要思想是动态规划(dp),而求最短路径需要不断松弛(熟悉spfa算法的可能熟悉松弛)。

    而算法的具体思想为:

    1. 邻接矩阵dist储存路径,同时最终状态代表点点的最短路径。如果没有直接相连的两点那么默认为一个很大的值(不要溢出)!而自己的长度为0.

    2. 第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改,这个长度就是说两点距离会不会因为新加入的点变得更短(a_k_b距离

    3. 而上述试探具体方法为遍历图中每一个点(i,j双重循环),判断每一个点对距离是否因为加入的点而发生最小距离变化。如果发生改变,那么两点(i,j)距离就更改。

    4. 重复上述直到最后插点试探完成。

    其中第三步的状态转移方程为:

    • dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
      其中dp[x][y]的意思可以理解为x到y的最短路径。所以dp[i][k]的意思可以理解为i到k的最短路径dp[k][j]的意思可以理解为k到j的最短路径.

    咱们图解一个案例:

    1a3f749e64356d7bf97bcae5ec55373d.png
    在这里插入图片描述

    默认的最短长度初始为邻接矩阵初始状态

    • 加入第一个节点1,大家可以发现,由于1的加入,使得本来不连通的2,3点对和2,4点对变得联通,并且加入1后距离为当前最小。(可以很直观加入5之后2,4,更短但是还没加入)。为了更好的描述其实此时的直接联通点多了两条。(2,3)和(2,4).我们在dp中不管这个结果是通过前面那些步骤来的,但是在这个状态,这两点的最短距离就算它!

      cb5a25c0955af652cb88e77a21a37a90.png
      在这里插入图片描述
    • 同时你可以发现加入1其中也使得3,1,4这样联通,但是 3,1,4联通的话距离为9远远大于本来的(3,4)为2,所以不进行更新。

    • 咱们继续加入第二个节点。在加入的初始态为:

      76c482c9b38c6f0804969792fee511af.png
      在这里插入图片描述
    • 进行遍历插入看看是否更新节点

      e7d309056a67a9e7f6218075f5a8f309.png
      在这里插入图片描述


      实际上这个时候图中的连线就比较多了。当然这些连线都是代表当前的最短路径。 这也和我们的需求贴合,我们最终要的是所有节点的最短路径。每个节点最终都应该有6条指向不同节点的边! 表示邻接矩阵的最终结果。

    至于算法的模拟两部核心已经告诉大家了,大家可以自行模拟剩下的。

    程序实现

    而对于程序而言,这个插入的过程相当简单。核心代码只有四行
    代码如下

    public class floyd {
        static int max = 66666;// 别Intege.max 两个相加越界为负
        public static void main(String[] args) {
            int dist[][] = {
                    { 0236, max, max }, 
                    { 20, max,max, 46 }, 
                    { 3, max, 02, max, max },
                    { 6, max, 2013 }, 
                    { max, 4, max, 10, max }, 
                    { max, 6, max, 3, max, 0 } };// 地图
            // 6个
            for (int k = 0; k 6; k++)// 加入滴k个节点
            {
                for (int i = 0; i 6; i++)// 松弛I行
                {
                    for (int j = 0; j 6; j++)// 松弛i列
                    {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
            // 输出
            for (int i = 0; i 6; i++) {
                System.out.print("节点"+(i+1)+" 的最短路径");
                for (int j = 0; j 6; j++) {
                    System.out.print(dist[i][j]+" ");
                }
                System.out.println();
            }
        }
    }

    结果为:

    71550e293bf2c89de2b56a0112799d9f.png

    可以自行计算,图和上篇的Dijkstra是一致的,大家可以自行比对,结果一致,说明咱么的结果成功的。

    当然,在你学习的过程中,可以在每加入一个节点插入完成后,打印邻接矩阵的结果,看看前两部和笔者的是否相同(有助于理解),如果相同,则说明正确!

    你可能还会有疑惑,那咱么就用一个局部性来演示一下,看其中AB最短距离变化情况祝你理解:

    0b160d9749dbfec7a7d5f6144e9d8af7.png
    在这里插入图片描述

    好啦,Floyd算法就介绍到这里,如果对你有帮助,请动动小手点个赞吧!蟹蟹。

    推荐阅读:数据结构能干吗,我花了一夜给女朋友写个走迷宫游戏最短路径—弄懂Dijkstra(迪杰斯特拉)算法一种非大小排序(先后关系排序)—拓扑排序数据结构与算法—深度、宽度优先(dfs,bfs)搜索哈夫曼树(最优二叉树)详解与构造写文没高质量配图?教你python爬虫绕过限制一键搜索下载图虫创意图片!一文搞懂简单数据结构—并查集(不相交集合)从阶乘、斐波那契、汉诺塔剖析彻底搞懂递归算法

    希望和各位共同进步!欢迎关注笔者公众号:bigsai

    c29d14b67f114ea1cfa82170cb1a0c3c.png

    展开全文
  • 请各位大佬,嘴下留情,不要喷我,没什么气度,会拉黑人这篇文章是关于图计算中单源最短路径问题,认识我的人朋友可能应该都知道我不是特别爱关注算法相关的问题,尤其是关于了解具体某一个算法的实现过程。...

    只是个菜鸡,请各位大佬,嘴下留情,不要喷我,没什么气度,会拉黑人

    这篇文章是关于图计算中单源最短路径问题,认识我的人朋友可能应该都知道我不是特别爱关注算法相关的问题,尤其是关于了解具体某一个算法的实现过程。作为一个数学不是特别好的菜鸡,我总觉得对于这种类似的问题就应该是不求甚解,点到即止,我又不是理论科学家或是研究人员,结果直接拿来用就完了。对于之前的我来说,一个成熟的算法就像是一个黑匣子。我给数据,它出结果,实现过程什么的完全不在乎。

    但是近段时间,在跟一些同学在微信群里聊天(我其实是在潜水),会出现知识断层。(后来也去查过这些我不知道的东西,发现跟我完全没有什么关系,实用主义又开始作祟)即便是这样,我也想本着提升自身的目的,还是要再下点功夫,从理论层面看看常用常见算法实现过程,不求能融会贯通,至少能一步步复现。这次援引的材料较多,主要的出版书籍有三本,分别是:《算法图解》《算法》(特别厚的那本橙书)以及《算法导论》。另外还有很多的网络资料,在文末贴出,我就一个Lego小人,站在Transformers的肩膀上前行。关于《算法导论》的看法。真的是一本讲的比较通透的书,推荐可以买来看看。至于《算法》,我表示没有什么想法,实现语言是Java,虽说算法都是通用的,但是近段时间用pyhton用的太久,不是特别想换Java,而且以后说不定没机会用Java。

    0 1Dijkstra Algorithm

    关于使用Dijkstra的条件背景,一般来说在一个图的数据类型中我们经常想去寻求的是一个最短路径。在没有权值(weight)的情况下,从一个节点(node)到另一个节点的开销就是1。从start节点到end节点,中间经历的线段数目就是从start节点到end节点的开销。但是,一般情况下图不可能没有权值的概念,从点A到点B是会有花费的,比如抽象成一个地图,从一个城市到另一个城市,所花费可能就是时间,或者路费。又比如抽象成一个交易图谱,先用物品A换取物品B,可能是等价交换,这个时候的花费是0,但更有可能是不等价交换,还需要加上一点钱的开销花费。如何用最少的时间到达目的地,如何用最少的钱换取到想要的物品,就是Dijkstra算法的作用。Dijkstra算法解决的是带权重的有向图上的单源最短路径问题,并且要求所有的权重都为非负值。

    b4533268c54296389cad04c9ddf9fa5b.png

    (图片来源:《算法导论》)

    这里先大致叙述下算法实现流程:

    ››››首先用散列表graph(在不同的语言中,散列表的实现形式不同,例如在python中散列表以字典的形式呈现)来记录这张图的数据。

    ››››用第二个散列表costs,来表示当前的节点到表中的可触及节点(当前节点的邻居节点)及花费,以及不可触及节点及花费(不可触及的节点花费即为∞)。这张表会随着算法的运行不断更新,更新的这个过程,会称之为“松弛”(后面会解释什么叫做“松弛”)。

    ››››用第三个散列表parents,来记录到达每个节点之前的前驱节点或者叫父节点,叫什么都好,主要就是指前一个节点。这张表是随着costs一起更新的。

    ››››每次计算当前花费最少的那个节点,算完之后,做上标记(例如放进一个列表中,表示已经计算过,Dijkstra算法对每个节点只算一次),避免算上环路(有环路一定不是最短路径)。

    ››››循环往复,直到所有节点全部算完。这样通过第三个parents散列表,就能够反推出整个图的从start节点到end节点的最短路径。


    松弛操作

    对于每个节点v来说,我们维持一个属性v.d,用来记录从源节点s到节点v的最短路径权重的上界。我们称v.d为s到v的最短路径估计。对一条边的(u,v)的松弛过程为:首先测试一下是否可以从对s到v的最短路径进行改善。测试的方法是,将从节点s到节点u之间的最短路径加上节点u与v之间的边权重,并与当前的s到v的最短路径估计进行比较,如果前者更小,则对v.d和v.π进行更新。

    《Introduction to Algorithms》

    其实“松弛”的操作,我觉得还挺好理解的。就像想象成从任意节点开始,我们要到另一个节点,但是我们还不知道抵达另一个节点的花费是多少,所以我们会预估一个花费出来,这里默认预估的是∞。那么,一旦我们发现有个有比∞更小的花费,那么我们就会更新costs和parents。就好像一根弦,我原来以为目标点很远,所以拉的很长,结果发现不需要那么远,于是就把这根弦给缩短了,这不就是“松弛”了吗?这种感性的理解方式,可能显得不那么学术,但是有用。

    我来做第一个字典,即graph的字典,它应该是这个样子的。

    Graph
    起始节点目标节点花费
    st10
    y5
    ty2
    x1
    yt3
    x9
    z2
    xz4
    zs7
    x6

    costs和parents的字典比较简单。costs左边是每个节点(除了start节点),右边一栏是到该节点的总共花费,意味着需要将之前经过的节点的花费都算上。parents实际上,就是最后生成路径的一个依据,字典左栏是每个节点,右栏是抵达该节点的前一个节点(父节点,前驱节点)。

    上代码

    graph = {}
    graph["s"] = {}
    graph["s"]["t"] = 10
    graph["s"]["y"] = 5
    graph["t"] = {}
    graph["t"]["y"] = 2
    graph["t"]["x"] = 1
    graph["y"] = {}
    graph["y"]["t"] = 3
    graph["y"]["x"] = 9
    graph["y"]["z"] = 2
    graph["x"] = {}
    graph["x"]["z"] = 4
    graph["z"] = {}
    graph["z"]["x"] = 6
    graph["t"]["s"] = 7

    infinity = float("infinity")

    costs = {}
    costs["s"] = 0
    costs["t"] = 10
    costs["y"] = 5
    costs["x"] = infinity
    costs["z"] = infinity

    parents = {}
    parents["s"] = "s"
    parents["t"] = "s"
    parents["y"] = "s"
    parents["x"] = None
    parents["z"] = None

    processed = []

    def find_lowest_cost_node(costs):
        lowest_cost = float("inf")
        lowest_cost_node = None
        # 遍历所有的节点
        for node in costs:
            cost = costs[node]
            # 如果当前的节点的开销更低,且未处理过
            if cost < lowest_cost and node not in processed:
                # 就将其视为开销最低的节点
                lowest_cost = cost
                lowest_cost_node = node
        return lowest_cost_node

    # 未处理的节点中找出开销最小的节点
    node = find_lowest_cost_node(costs)
    # 这个while循环在所有节点都被处理过后结束
    while node is not None:
        cost = costs[node]
        neighbors = graph[node]
        # 遍历当前节点的所有邻居
        for n in neighbors.keys():
            new_cost = cost + neighbors[n]
            # 如果经当单前节点前往该邻居更近
            if costs[n] > new_cost:
                # 就更新该邻居的开销
                costs[n] = new_cost
                # 同时将该邻居的父节点设置为当前节点
                parents[n] = node
        # 将当前节点标记为处理过
        processed.append(node)
        # 找出接下来要处理的节点并循环
        node = find_lowest_cost_node(costs)

    print(parents)
    print(costs)

    上面脚本运行的结果就是输出parents和costs的字典内容,可以发现结果和上图完全一样。

    {'s': 's', 't': 'y', 'y': 's', 'x': 't', 'z': 'y'}{'s': 0, 't': 8, 'y': 5, 'x': 9, 'z': 7}

    那么根据这个字典,就可以逆推出最短路径。比如,end节点如果是z,那么就要先到y节点,要到y节点,就要先到s节点,s就是起始节点,逆推完成。

    0 2Bellman-Ford Algorithm

    Bellman-Ford的使用背景是一般情况下的单源路径问题,并且这里的图可以包含负权重

    在任意含有V个顶点的加权有向图中给定起点s,从s无法到达任何负权重环,以下算法能够解决其中的单点最短路径问题:将distTo[s]初始化为0,其他distTo[]元素初始化为无穷大。以任意顺序放松有向图的所有边,重复V轮。Bellman-Ford算法所需的时间和EV成正比,空间和V成正比

    《Algorithm(4 Edition)》

    简单阐述一下Bellman-Ford算法的过程:

    ››››首先生成一个散列表costs,键为每个顶点,值为权值,因为一开始不知道究竟需要多少权值,所以默认为∞

    ››››再生成一个散列表parents,键为每个顶点,值为该节点前驱节点,默认值均设置为None

    ››››做循环,循环的次数依图的顶点数而定,N个节点便循环N-1次,每次遍历所有的节点,并且做松弛操作,将结果更新到两个散列表中

    ››››N-1次循环完毕后,再做一次,如果发现依然能够进行松弛操作,说明图中有权值为负的环路

    python实现代码如下,这里有个小问题,Alan还是把问题想复杂了,本来打算按照自己的想法来实现Bellman-Ford,最后把自己绕晕了。在CSDN上看到了作者popoffpopoff的文章,读完之后醍醐灌顶,稍作修改,略加注释,贴在下面。

    graph = {

        "a":{"b":-1, "c":4},
        "b":{"c":3, "d":2, "e":2},
        "c":{},
        "d":{"b":1, "c":5},
        "e":{"d":-3}
    }

    def Bellman_Ford(graph, sourceNode):
        # 两个散列表,分别为costs和parents
        costs = {}
        parents = {}

        infinity = float("inf")

        # 初始化每个顶点的权值初始值设为∞,前驱节点设置为None
        for v in graph:
            costs[v] = infinity
            parents[v] = None

        # 起始节点的权值或者说花费置0
        costs[sourceNode] = 0
     
        # 一共有N个节点便循环N-1次,每次循环所有的节点,并做松弛操作
        for i in range(1, len(graph)):
            for u in graph:
                for v in graph[u]:
                    if costs[v] > graph[u][v] + costs[u]:
                        costs[v] = graph[u][v] + costs[u]
                        parents[v] = u
        
        # 全部做完之后,再做一遍松弛
        for u in graph:
            for v in graph[u]:
                # 如果还是能够实现松弛,说明图中有负权值环路
                if costs[v] > costs[u] + graph[u][v]:
                    return None, None
     
        return costs, parents
     
    costs, parents = Bellman_Ford(graph, 'a')

    print(costs)
    print(parents)

    这里的输出结果如下所示:

    {'a': 0, 'b': -1, 'c': 2, 'd': -2, 'e': 1}{'a': None, 'b': 'a', 'c': 'b', 'd': 'e', 'e': 'b'}

    依旧是根据parents字典能够反推出最小路径。到这里可以开始做总结了:

    1. Dijkstra算法和Bellman-Ford算法的差别主要在于前者对于图中的权值有一定的要求,即不能包含负的权值边线。而Bellman-Ford虽然能够允许图中包含负的权值,但是运行的时间显然要比前者要慢上不少。可以预见的到,实际应用中,应该较少的情况会用Bellman-Ford算法。

    2. Dijkstra对每个节点都只算一次,而Bellman-Ford会重复计算,这是两者在运行时间上产生差距的重要原因。

    [援引资料]

    1. 《算法图解》Aditya Bhargava 2017年3月第1版

    2. 算法(第4版)》Robert Sedgewick、Kevin Wayne 2012年10月第1版

    3. 《算法导论(第3版)》Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein 2013年1月第1版

    4. https://blog.csdn.net/popoffpopoff/article/details/81940372

    5. https://juejin.im/post/5b77fec1e51d4538cf53be68

    6. https://www.cnblogs.com/gaochundong/p/bellman_ford_algorithm.html

    展开全文
  • 【机器人】路径规划 - 图解A* 搜索算法 A* 算法是启发式搜索算法,是根据Dijkstra算法改进而来。问题引入如下图所示,S为起始(start)节点,G为目标(goal)节点。节点之间连线是两点的路径长度,如A到E的路径长度c...

    b5f31d9e8a87774657befd3b702bfdc5.png

    【机器人】路径规划 - 图解A* 搜索算法

    A* 算法是启发式搜索算法,是根据Dijkstra算法改进而来。
    问题引入
    如下图所示,S为起始(start)节点,G为目标(goal)节点。

    • 节点之间连线是两点的路径长度,如A到E的路径长度c(A,E) = 9。
    • 节点旁的h值时当前节点到达目标节点(G)的预估值,如h(A)=15, 表示从当前点A到达目标点G的估计路径长度为15,此处h(x)即为启发函数,启发函数的设计有很多方法,具体可参考链接,此处不再扩展。
    • 从起点S到达当前节点x的路径长度表示为g(x) 。
    • 从起点S到达目标G并经过点x的估计距离长度表示为f(x) = g(x) + h(x),该公式是A*算法的核心公式。
    • A*算法通过不断的选择估计距离f最小的节点,逐渐构建最短路径。

    c241a4b594013e8df9a4974e229b21bf.png


    逻辑流程
    创建两个集合OPEN集,CLOSED集,算法核心是从OPEN集中选择最优(f值小最优,或f相同时,h小的更优)的节点到CLOSED集中,然后将其后继节点放入OPEN集中,然后重复操作选取最优节点,直到到达目标,或者OPEN为空为止。最后再CLOSED集中根据目标G所包含的前序节点逆序查找最后到达起点S,这个链路的逆序即最优路径,具体流程如下图。

    c71ec3f351c36018eae4113696b37f0d.png


    搜索过程
    以下是前面网络的搜索过程展开图。
    组合块中:

    • 灰色为前序节点
    • 蓝色当前节点x
    • g:起点S到当前节点x的路径距离。
    • h:当前节点x到终点G的估计距离
    • f:起点S途径x到达终点G的估计距离,即 f = g + h
    • 绿色框为当前OPEN集合中的最优节点
    • 红色框表示当前OPEN集合中需要被删除的节点

    在OPEN、CLOSED中每一行表示一次完整迭代完成时两集合中的节点集合。
    最后的最优路径是:S->B->F->k->G
    注:当两个节点f相同时,h小的更优

    d1179d9897988f65cf063b4098986492.png

    【算法】图解A* 搜索算法 https://blog.csdn.net/JasonZhu_csdn/article/details/86266228

    展开全文
  • 本文力荐 | 28天玩转算法训练营02期首图 |何塞·维莱加斯·科尔德罗编辑 | 林瑟程序员都知道的三本算法书《算法》、《算法导论》、《算法图解》,但真正能读完的人少之又少。比如:“看了半年的《算法》这本书,才看...
  • 它满足下列性质:输入:有零个或多个输入量 输出:产生至少一个输出量 确定性:算法的指令清晰、无歧义 有限性:算法的指令执行次数有限,执行时间有限我们在使用计算机解决产问题的过程可以分为下面五个步骤:问题...
  • Dijkstra算法证明图解

    2021-02-09 11:26:30
    目录前言:算法步骤参数说明算法描述算法过程图解算法可行性证明一.数学归纳法:假设前提:归纳证明:二.贪吃蛇法(个人理解): 前言: Dijkstra算法算是比较经典的一个求单源最短路径的一个算法了,有向图和无向图...
  • Dijkstra算法

    2017-02-05 14:17:40
    Dijkstra算法过程图解: 来自:http://blog.csdn.net/cjc211322/article/details/24932691 http://wenku.baidu.com/view/370cf661caaedd3383c4d38b.html
  • Dijkstra算法-(迪杰斯特拉)算法之迭代实现 Dijkstra算法-(迪杰斯特拉)算法之优先队列实现
  • Dijkstra算法图文详解和C++代码

    千次阅读 2019-06-04 15:24:48
    文章目录1 Dijkstra算法基本原理2 算法过程图解1(有向图)3 算法过程图解2(无向图)4 C++代码4.1 案例1代码4.2 案例2邻接矩阵定义4.3 案例2代码Dijkstra算法 1 Dijkstra算法基本原理 Dijkstra算法是根据贪心算法...
  • Dijkstra算法实现最短路径概述Dijkstra算法思想Dijkstra算法过程设置关键数组具体图解过程Dijkstra算法实现Dijkstra算法完整过程运行结果分析 概述 现在给出一个无向网G现在让你从0点开始 求出到每个点的最短路径 ...
  • 整体来看dij就是从起点开始扩散致整个图的过程,为什么说他稳定呢,是因为他每次迭代,都能得到至少一个结点的最短路。(不像SPFA,玄学复杂度) 但是他的缺点就是不能处理带负权值的边,和代码量稍稍复杂。 dij算法...
  • 最短路径算法一之Dijkstra...Dijkstra算法求最短路径具体过程图解 结合上图具体搜索过程,我绘出下表,方便理解该过程!下表是按照上图的搜索过程来绘制的,当然,存储图的时候,节点存储顺序的不同也会导致搜索的
  • Dijkstra 算法简介 1. 算法步骤 找出起点权重值最低的节点,即消耗最小权重值可达的节点; 对于该节点的邻居,检查是都有前往它们的权重值更小的路径,如果有,则更新其开销 重复这个过程,直到对每个节点都这样做...
  • 好吧,这是我第一次写最短路问题,之前看一个人的博客,结果那个人的博客有问题。...至于过程介绍,大家可以看一下这个博客,我就不累赘介绍了;有很详细的图解; 链接:http://blog.csdn.net/stanfordzhang/article
  • 实例图解Dijkstra

    2019-01-15 23:42:10
    关于Dijkstra算法的算法描述网络上太多了,在此就不赘述了,直接用一个实例讲解其算法执行过程图解是考试前临时做的,有些粗糙,大家凑合看看,跟着手写一遍就理解了 题目:求下图中v0到其余点的最短路径 以下...
  • 使用条件:单源最短路径,适用于边权非负的情况Dijkstra算法求最短路径具体过程图解 结合上图具体搜索过程,我绘出下表,方便理解该过程!下表是按照上图的搜索过程来绘制的,当然,存储图的时候,节点存储顺序的...
  • dijkstra算法介绍:是从一个顶点到其余各顶点的[最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。 狄克斯特拉算法包含4个步骤 (1) 找出...
  • 狄克斯特拉算法 一、简介: 是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止 ...三、图解:...
  • 1、狄克斯特拉算法Dijkstra's algorithm) 对于广度优先搜索找出的路径,只适用于图中边的权值都相同的情况,如果权值不相同,可能找出的未必是最短路径。如图:对于不同权值的图,我们使用狄克斯特拉算法寻找...
  • Floyd算法是另一种经典的最短路径算法,将每个顶点作为源点,分别使用Dijkstra算法Dijkstra算法是对单源点求得的最短路径,现在我们基于Dijkstra算法去实现对每一个顶点求得最短路径,此时我们使用的算法...
  • dijkstra求多条最短路径(附源码)

    千次阅读 2016-11-06 16:11:00
    手绘了半天图实在是没精力对dijkstra做基本介绍了,本文默认大家对dijkstra已经有了基本的了解。...2.接下来是多条最短路径dijkstra算法的运行过程图解,圆圈中第一个数字是走到当前节点时花费的co
  • 几乎就是套模板了,可以参考Dijkstra算法图解过程中犯的错: 反图: 一开始没弄清楚题意,以为先求一遍1点到所有点的最短路之和,再求n点到所有点的最短路之和。其实是要将边反过来。 long long: int是不够用...
  • 目录一、弗洛伊德(Floyd)算法介绍二、弗洛伊德算法 VS 迪杰斯特拉算法三、弗洛伊德(Floyd)算法过程四、弗洛伊德(Floyd)算法——应用场景(最短路径问题)五、弗洛伊德(Floyd)算法——解决最短路径问题思路图解六、...
  • 最短路---Dijkstra&Floyd

    2020-03-07 18:35:52
    算法图解 今天就不手撸画图了,看到了一个很详尽并且很规整的图,直接拿来用。 在这个有向图中有6个顶点V0-V5。关于图的内容就不多说了背景故事也懒得编了就来说说这个图用Dijkstra的遍历过程吧。 首先大家要明白...
  • 图论-单源最短路径(Dijskal算法

    千次阅读 多人点赞 2020-10-11 10:41:38
    不允许你还不会最短路径,详细图解,一定看得懂的! HDU-2544 最短路 ...Dijkstra算法是图论中用来求单源最短路径的经典算法,复杂度可以优化到O(mlog(n))。从整体上看就是从一个起点,扩散到整个图的过程
  • ps:Prim算法看起来与Dijkstra有些相似,笔者将在另一篇博客里对它们的区别进行分析 Kruskal-克鲁斯卡尔算法 思路: (1)将边按权值从小到大的顺序添加到新图中,保证添加的过程中不会形...
  • 数据结构与算法—常用十种算法8迪杰斯特拉(Dijkstra)算法 声明:以下是学的尚硅谷网课并结合网上资料所记的笔记。可能会有一些错误,发现了会...图解参考该文章 Dijkstra算法(三)之 Java详解 代码 import java.util.A
  • 概述 银行家算法是荷兰学者Dijkstra为...过程演示图解 假定有五个进程{P0,P1,P2,P3,P4}和三类资源{A,B,C},各种资源的数量分别为10、5、7。在T0时刻的资源分配情况如下 T0时刻的安全性 P1发出请求向量Request1(1,

空空如也

空空如也

1 2
收藏数 29
精华内容 11
关键字:

dijkstra算法过程图解