《算法图解》note 7 狄克斯特拉算法1.狄克斯特拉算法简介2.代码实例

这是《算法图解》的第7篇读书笔记。其主要内容是简述狄克斯特拉算法。

1.狄克斯特拉算法简介

迪克斯特拉(dijkstra)) 算法用于找出有向无环图(DAG)中两点的最短路径。 对于无权重的有向无环图,狄克斯特拉算法的用途等效于广度优先搜索(BFS)。 对于有权重的图: 若边的权重是相等的正数,其用途等效于广度优先搜索。 若边的权重不等且仅权重均为正数,狄克斯特拉算法能出两点间的最短路径。 若边的权重有负数,则狄克斯特拉算法是不适用的。

2.代码实例

现在将通过python代码找出以下DAG中从A点至E点的最短路径。

DAG.jpg

代码如下:

#狄克斯特拉算法

#找出costs中未被标记且值最小的节点
def find_shortest_node(costs,processed):
    shortest_d=float('inf')
    shortest_node=None
    for node, d in costs.items():
        if d<shortest_d and node not in processed:
            shortest_d=d
            shortest_node=node
    return shortest_node
    

#狄克斯特拉算法主体函数
#while循环中,根据当前节点与其邻居节点的距离,尝试到达邻居节点的最短距离
#若找到,更新costs字典中,邻居节点的最短距离,同时将邻居节点的父节点设置为当前节点
def dikjstra(G,costs,parent,processed):
    cur_node=find_shortest_node(costs,processed)
    cur_d=costs[cur_node]
    while cur_node:
        for n,l in G[cur_node].items():
            if l+cur_d<costs[n]:
                costs[n]=l+cur_d
                parent[n]=cur_node
        processed.add(cur_node)
        cur_node=find_shortest_node(costs,processed)


#图
G={
    'A':{'B':3,'C':7},
    'B':{'C':2,'D':4},
    'C':{'D':1,'E':6},
    'D':{'E':3},
    'E':{}
}

#记录从起点到达当前节点的最短距离
costs={
    'A':0,
    'B':float('inf'),
    'C':float('inf'),
    'D':float('inf'),
    'E':float('inf'),
}

#在到达当前节点的距离最短路线下,当前节点的父节点
parent={}

#记录已被处理过的节点
processed=set()

#运行狄克斯特拉算法
dikjstra(G,costs,parent,processed)
#根据运算结果显示最短路径
shortest_path=[]
cur_dot='E'
while cur_dot:
    shortest_path.append(cur_dot)
    cur_dot=parent.get(cur_dot)
shortest_path.reverse()
print(shortest_path)

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能

Apache Spark中的决策树

原文地址:https://dzone.com/articles/decision-trees-in-apache-spark

8168
来自专栏小鹏的专栏

04 Support Vector Machines

Introduction:         支持向量机是二进制分类的方法。 基本思想是在两个类之间找到线性分离线(或超平面)。 我们假设二进制类目标是-1或1,...

30410
来自专栏生信技能树

比较不同的对单细胞转录组数据寻找差异基因的方法

背景介绍 如果是bulk RNA-seq,那么现在最流行的就是DESeq2 和 edgeR啦,而且有很多经过了RT-qPCR 验证过的真实测序数据可以来评价不同...

47110
来自专栏生信技能树

比较不同的对单细胞转录组数据normalization方法

使用CPM去除文库大小影响 之所以需要normalization,就是因为测序的各个细胞样品的总量不一样,所以测序数据量不一样,就是文库大小不同,这个因素是肯定...

4866
来自专栏ascii0x03的安全笔记

利用Python sklearn的SVM对AT&T人脸数据进行人脸识别

要求:使用10-fold交叉验证方法实现SVM的对人脸库识别,列出不同核函数参数对识别结果的影响,要求画对比曲线。 使用Python完成,主要参考文献【4】...

4268
来自专栏IT派

用DaPy进行机器学习

DaPy自带了少量著名的数据集,比如用于分类问题的红酒分类和鸢尾花数据集。 接下来,我们首先启动一个Python Shell并加载作为例子的红酒数据集:

923
来自专栏ATYUN订阅号

使用Python进行人脸聚类的详细教程

思考下面这个场景:两名劫匪在抢劫波士顿或纽约等繁华城市的银行。银行的安全摄像头工作正常,捕捉到了抢劫行为,但劫匪戴着头套,没办法看到他们的脸。

1072
来自专栏生信技能树

差异分析得到的结果注释一文就够

通过前面的讲解,我们顺利的了解了GEO数据库以及如何下载其数据,得到我们想要的表达矩阵,也学会了两个常用的套路分析得到的表达矩阵,就是GSEA分析和差异分析。 ...

4135
来自专栏有趣的Python

15- 深度学习之神经网络核心原理与算法-多gpu实现CNN图片分类

2753
来自专栏wym

分支限界法

    我们可以按照行优先和列优先。 这里我们采用行优先,找出每一行最小值求和,那么最优解一定不会大于这个值,

682

扫码关注云+社区