本站消息

站长简介/公众号


站长简介:逗比程序员,理工宅男,前每日优鲜python全栈开发工程师,利用周末时间开发出本站,欢迎关注我的微信公众号:幽默盒子,一个专注于搞笑,分享快乐的公众号

  价值13000svip视频教程,python大神匠心打造,零基础python开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2020-07(10)

2020-08(50)

Dijkstra算法

发布于2021-04-17 21:08     阅读(871)     评论(0)     点赞(3)     收藏(1)



前言

Dijkstra算法常用于求解单源最短路径,即边上带有权值的图(有向图或者无向图)中的一点到其他各点的最短距离。

下面以一张抽象为无向图的校园地图为例,介绍Dijkstra算法的原理和python代码实现。

无向图如下图所示,要求计算16号红色节点到其他各个节点的最短路径。:

图中各条边的权值(即路径的长度)被记录在excel表格中,格式如下:


一、算法原理

算法流程如下(图源自《算法导论》)。伪代码中 G G G表示图, V V V表示 G G G中节点的集合, v v v表示 V V V中的节点, s s s表示起点, v . d v.d v.d表示节点 v v v距离起点 s s s的距离, v . π v.\pi v.π表示在包含 v v v的最短路径中 v v v前面的节点。

S S S Q Q Q是两个点集, S S S中的点表示已经找到最短路径, Q Q Q中的点表示还没有找到最短路径。

EXTRACT-MIN( Q Q Q)表示从 Q Q Q中选择距离起点 s s s最近的一点。

算法执行流程:

1. 初始化,把 V V V中的每个节点到 s s s的距离初始化为无穷大,前节点初始化为空;把 s . d s.d s.d初始化为0,表示节点 s s s距离 s s s的距离为0; S S S初始化为空, Q Q Q初始化为全集 V V V

2. 执行while循环,当 Q Q Q不为空时,从 Q Q Q中取出距离起点 s s s最近的点 u u u,添加到 S S S中,然后重新计算 V V V中和 u u u相邻的点到 s s s的最短距离。(已经添加到 S S S中的点,最短距离已经计算得到,通过 u u u不会得到更短的距离。)

3. Q Q Q中节点为空,退出循环。

初始化(INITIALIZE)函数:

RELAX函数:

下面举一个具体的例子:

1. 初始化, S S S为空, Q Q Q V V V

2. 第1次while循环, u = s u = s u=s s s s添加到 S S S中。更新 s s s t , y t,y ty的距离。

3. 第2次while循环, u = y u = y u=y y y y添加到 S S S中。更新 s s s t , x , z t,x,z txz的距离。

4. 第3次while循环, u = z u = z u=z z z z添加到 S S S中。更新 s s s x x x距离。( s s s已经在 S S S中了)

5. 第4次while循环, u = t u = t u=t t t t添加到 S S S中。更新 s s s x x x的距离。


二、代码实现

import numpy as np
import xlrd

class vertex:
    id = 0
    pre = 0
    d = float('inf')#无穷大
    def __init__(self, a, b, c):
        self.id = a
        self.pre = b
        self.d = c
    def __lt__(self, other):#定义比较函数,排序用,把d作为排序的关键字。
        return self.d < other.d
    
class Graph:
    E = np.zeros((36, 36), dtype = np.float)
    V = []
    Adj = []
    
G = Graph()#定义一个“Graph”实例

for i in range(1, 36):#把节点加入G的点集中
    p = vertex(i, 0, float('inf'))
    G.V.append(p)

#读取w矩阵
w = np.zeros((36, 36), dtype = np.float)
data = xlrd.open_workbook('D:\\Softwarefiles\\tex\\RoadAndDistance.xls')
table = data.sheet_by_name('Sheet1')

for i in range(1, 36):
    for j in range(1, 36):
        if i == j:
            w[i, j] = 0.0
        else:
            w[i, j] = float('inf')

for k in range(1, table.nrows):
    i = int(table.cell(k, 0).value)
    j = int(table.cell(k, 1).value)
    w[i, j] = table.cell(k, 2).value
    w[j, i] = table.cell(k, 2).value
    
G.Adj.clear()
G.Adj.append([])#占空位,使得节点编号和列表下标相对应。
for i in range(1, 36):
    G.Adj.append([])
    for j in range(1, 36):
        if w[i, j] != float('inf'):
            G.Adj[i].append(G.V[j-1])#下标从0开始,比id小1

def INITIALIZE_SINGLE_SOURCE(G, s):
    it = iter(G.V)
    for v in it:
        v.d = float('inf')
        v.pre = 0
    s.d = 0

def RELAX(u, v, w):
    if v.d > u.d + w[u.id, v.id]:
        v.d = u.d + w[u.id, v.id]
        v.pre = u.id
        
def EXTRACT_MIN(Q):#排序后,d最小的节点在Q[0]的位置,赋值给u,删除Q[0]
    Q.sort()
    u = Q[0]
    del Q[0]
    return u

S = []
def DIJKSTRA(G, w, s):
    INITIALIZE_SINGLE_SOURCE(G, s)
    Q = G.V
    while(len(Q)):
        u = EXTRACT_MIN(Q)
        S.append(u)
        it = iter(G.Adj[u.id])
        for v in it:
            RELAX(u, v, w)

s = G.V[15]#下标从0开始,比id小1,id为16,对应下标为15。
DIJKSTRA(G, w, s)

it = iter(S)#打印出路径
for v in it:
    print(v.d, v.id, v.pre)

三、总结

仔细分析可以发现,Dijkstra算法和BFS(宽度优先搜索)有相似之处,当每条路径的权值变为相同时(比如都为1),Dijkstra算法访问节点的顺序甚至可以和BFS一样!究其原理,BFS使用一个队列存储节点,Dijkstra算法使用一个类似于“小根堆”的数据结构存储节点。而两者扩展节点的方式都是一样的。


参考资料

【1】introduction to algorithms (3rd edition)

原文链接:https://blog.csdn.net/weixin_45925418/article/details/115695228






所属网站分类: 技术文章 > 博客

作者:丸子

链接:https://www.pythonheidong.com/blog/article/940014/ac2798767b0713a71904/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

3 0
收藏该文
已收藏

评论内容:(最多支持255个字符)