前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[图]最短路径-Dijkstra算法

[图]最短路径-Dijkstra算法

作者头像
王荣胜
发布2020-03-13 17:40:27
7K0
发布2020-03-13 17:40:27
举报
文章被收录于专栏:王荣胜的专栏文章分享

迪杰斯特拉算法(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)

代码语言:javascript
复制
# 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)
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-01-19,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一.最短路径问题的求解
  • 二.Dijkstra算法
    • 1.算法思路
      • 2.算法图解
        • 3.代码实现(python)
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档