Python语言实现Dijkstra算法

week

发布于 2018-08-24 14:22:06

2.8K0

发布于 2018-08-24 14:22:06

文章被收录于专栏：用户画像

摘要

Dijkstra算法是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。

其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。

1 算法思想

1.1 总体思路

Dijkstra最短路经算法是一种单源最短路径，针对的是非负权边。所谓单源最短路径就是指定一个出发顶点，计算从该源顶点出发到其他所有顶点的最短路径。按路径长度递增次序产生算法：把顶点集合V分成两组：（1）S：已求出的顶点的集合（初始时只含有源点V0）（2）V-S=T：尚未确定的顶点集合将T中顶点按递增的次序加入到S中，保证：（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的长度 T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度

依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和

1.2 算法流程图

以下图，从顶点A作为出发点为例，来说明Dijkstra算法过程。

1.2.1 初始化

设置两个集合，S集合和U集合。S集合初始只有源顶点即顶点A，V集合初始为除了源顶点以外的其他所有顶点。

设置一个数组dist用来表示顶点A到其他顶点的最短距离，初始化为-1（表示无穷大）。

1.2.2 集合S加入C

遍历集合V中与A直接相邻的顶点，找出当前与A距离最短的顶点。发现： A->C = 3 A->B = 6 于是乎，将C移除集合V将其加入到集合S中，于此同时更新dist数组： dist[C] = 3 dist[B] = 6

更新结果如下：

1.2.3集合S加入B

遍历集合V中与C相邻的顶点，发现 C->B = 2 ， C->D = 3 ， C->E = 4，由于目前dist中最短距离 A->C = 3 即 dist[C] = 3，那么： A->B = 3 + 2 =5 A->D = 3 + 3 = 6 A->E = 3 + 4 = 7 而目前在dist中： A->B = 6 A->D = -1 A->E = -1 经过比较，将顶点B加入集合S中，并将其从V集合中删除，更新dist中A->B ，A->D，A->E的记录即 dist[B] = 5 dist[D] = 6 dist[E] = 7

更新结果如下：

1.2.4 集合S加入D

遍历集合V中与B相邻的顶点，发现 B->D = 5，在dist中可以查到最短距离A->B = 5，那么： A->D = 5 + 5 = 10 而目前在dist中： A->D = 6

所以，将D加入到集合S中，并将其从V集合中删除，不更新dist数组相应的值，因为dist中A->D即 dist[D] 更短。更新后如下

1.2.5 集合S加入E

遍历集合V中与D相邻的顶点，发现 D->E = 2 ， D->F = 3，在dist中可以查到最短距离A->D = 6，那么： A->E = 6 + 2 = 8 A->F = 6 + 3 = 9 而在dist中： A->E = 7 A->F = -1 所以将E从集合V中删除并加入到集合S中，并更新dist中的：dist[F] = 9

1.2.6 集合S加入E

由于到目前为止只剩下顶点F，所以将F也加入到集合S中，至此算法运行结束。

由此，dist数组就是表示从源点A出发到达其他各个顶点的最短路径，比如 A->F，dist[F] = 9。

1.3 算法运行时间复杂度分析

Dijkstra最短路经算法时间复杂度为o(n^2)

2 程序代码说明

2.1 数据结构说明

图：是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。

2.2 函数说明

import networkx as nx

def Dijkstra(G,start,end):
    RG = G.reverse(); dist = {}; previous = {}
    for v in RG.nodes():
        dist[v] = float('inf')
        previous[v] = 'none'
    dist[end] = 0
    u = end
    while u!=start:
        u = min(dist, key=dist.get)
        distu = dist[u]
        del dist[u]
        for u,v in RG.edges(u):
            if v in dist:
                alt = distu + RG[u][v]['weight']
                if alt < dist[v]:
                    dist[v] = alt
                    previous[v] = u
    path=(start,)
    last= start
    while last != end:
        nxt = previous[last]
        path += (nxt,)
        last = nxt
    return path

3 实验结果

3.1 测试数据

G=nx.DiGraph()
G.add_edge(0,1,weight=80)
G.add_edge(1,2,weight=50)
G.add_edge(1,3,weight=30)
G.add_edge(3,2,weight=10)
G.add_edge(2,4,weight=20)
G.add_edge(2,5,weight=30)
G.add_edge(4,5,weight=10)
G.add_edge(5,3,weight=5)
G.add_edge(2,6,weight=10)
G.add_edge(4,6,weight=10)
G.add_edge(3,6,weight=25)
G.add_edge(5,6,weight=35)

rs=Dijkstra(G,0,6)
print(rs)