专栏首页王荣胜的专栏文章分享[图]最短路径-Dijkstra算法

[图]最短路径-Dijkstra算法

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。 -来自百度百科

一.最短路径问题的求解

1、单源最短路径用Dijkstra算法;

2、所有顶点间的最短路径用Floyd算法。

二.Dijkstra算法

开始之前我们需要知道的一些知识点:

1.Dijkstra算法只能用于边权为正的图中,时间复杂度为O(n^2);

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

Dijikstra算法所求解的问题是:大概有这样一个有权图,Dijkstra算法可以计算任意节点到其他节点的最短路径。

案例图

1.算法思路

1.指定一个节点,例如我们要计算 'A' 到其他节点的最短路径;

2.引入两个集合(S、U),S集合包含已求出的最短路径的点(以及相应的最短长度),U集合包含未求出最短路径的点(以及A到该点的路径,注意 如上图所示,A->C由于没有直接相连 初始时为∞);

3.初始化两个集合,S集合初始时 只有当前要计算的节点,A->A = 0;

4.U集合初始时为 A->B = 4, A->C = ∞, A->D = 2, A->E = ∞;

5.从U集合中找出路径最短的点,加入S集合,例如 A->D = 2;

6.更新U集合路径,if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' ) 则更新U;

7.循环执行 4、5 两步骤,直至遍历结束,得到A 到其他节点的最短路径。

2.算法图解

1.选定A节点并初始化,如上述步骤3所示;

图解1

2.执行上述 4、5两步骤,找出U集合中路径最短的节点D 加入S集合,并根据条件 if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' ) 来更新U集合;

图解2

3.这时候 A->B, A->C 都为3,没关系。其实这时候他俩都是最短距离,如果从算法逻辑来讲的话,会先取到B点。而这个时候 if 条件变成了 if ( 'B 到 C,E 的距离' + 'AB 距离' < 'A 到 C,E 的距离' ) ,如图所示这时候A->B距离 其实为 A->D->B;

图解3

4.思路就是这样,往后就是大同小异了;

图解4

5.算法结束。

图解5

采用表格表示为:

<a href="https://study.sqdxwz.com/usr/uploads/2019/10/3387651027.jpg" class="highslide" onclick="return hs.expand(this,{slideshowGroup:'images'})"><img src="https://study.sqdxwz.com/usr/uploads/2019/10/3387651027.jpg" height="330" width="495"></a>

3.代码实现(python)

# dijkstra算法实现,有向图和路由的源点作为函数的输入,最短路径最为输出
def dijkstra(graph,src):
    # 判断图是否为空,如果为空直接退出
    if graph is None:
        return None
    nodes = [i for i in range(len(graph))]  # 获取图中所有节点
    visited=[]  # 表示已经路由到最短路径的节点集合
    if src in nodes:
        visited.append(src)
        nodes.remove(src)
    else:
        return None
    distance={src:0}  # 记录源节点到各个节点的距离
    for i in nodes:
        distance[i]=graph[src][i]  # 初始化
    # print(distance)
    path={src:{src:[]}}  # 记录源节点到每个节点的路径
    k=pre=src
    while nodes:
        mid_distance=float('inf')
        for v in visited:
            for d in nodes:
                new_distance = graph[src][v]+graph[v][d]
                if new_distance < mid_distance:
                    mid_distance=new_distance
                    graph[src][d]=new_distance  # 进行距离更新
                    k=d
                    pre=v
        distance[k]=mid_distance  # 最短路径
        path[src][k]=[i for i in path[src][pre]]
        path[src][k].append(k)
        # 更新两个节点集合
        visited.append(k)
        nodes.remove(k)
        print(visited,nodes)  # 输出节点的添加过程
    return distance,path
if __name__ == '__main__':
    graph_list = [ [0, 2, 1, 4, 5, 1],
            [1, 0, 4, 2, 3, 4],
            [2, 1, 0, 1, 2, 4],
            [3, 5, 2, 0, 3, 3],
            [2, 4, 3, 4, 0, 1],
            [3, 4, 7, 3, 1, 0]]

    distance,path= dijkstra(graph_list, 0)  # 查找从源点0开始带其他节点的最短路径
    print(distance,path)

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Github界面简介

    Github网站上方,会有一个常驻工具栏,在首页和在仓库,工具栏会稍微有些许不同:

    王荣胜
  • Win10配置Java开发环境

    软件开发环境,是一个程序的运行的支撑,Java作为近年来最热门的编程语言之一,越来越多的新人程序员选择Java来学习,它的开发环境搭建也是学习和使用这一编程语言...

    王荣胜
  • [图]最短路径-Floyd算法

    <!--more--> > Floyd算法(Floyd-Warshall algorithm)又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之...

    王荣胜
  • 算法导论系列:贪心算法(2)

    现在我们假设景点地图如上所示,从起点到下一个点都会有具有方向路径和相应的权重,我们可以使用矩阵进行表示,如下图所示:

    云时之间
  • 算法导论系列:贪心算法(2)

    现在我们假设景点地图如上所示,从起点到下一个点都会有具有方向路径和相应的权重,我们可以使用矩阵进行表示,如下图所示:

    云时之间
  • 从图灵到高德纳:《算法分析导论》作者师承考据

    普林斯顿大学计算机系创始人,在斯坦福大学师从D. E. Knuth院士;曾任Adobe Systems公司董事会成员,并在Xerox PARC、IDA和INRI...

    用户1682855
  • 深度学习|神经网络模型求解思路总结

    《实例》阐述算法,通俗易懂,助您对算法的理解达到一个新高度。包含但不限于:经典算法,机器学习,深度学习,LeetCode 题解,Kaggle 实战。期待您的到来...

    double
  • 认识一位大佬,在微信团队工作了8年

    今天给大家推荐一个技术大牛:大飞,也就是我前两天转载《一行代码引发的恐惧》的作者,文章写的特别棒。

    纯洁的微笑
  • 机器视觉方向的21种常用算法

    https://jingyan.baidu.com/article/cbf0e500eb95582eaa28932b.html

    智能算法
  • 关于网络互连设备中继器、网桥、路由器、网关的分享

    由于传输线路噪声的影响,承载信息的数字信号或模拟信号只能传输有限的距离,中继器的功能是对接收信号进行再生和发送,从而增加信号传输的距离。它是最简单的网络互连设备...

    用户7053485

扫码关注云+社区

领取腾讯云代金券