《算法图解》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 条评论
登录 后参与评论

相关文章

来自专栏Python私房菜

用Python写算法 | 蓄水池算法实现随机抽样

现在有一组数,不知道这组数的总量有多少,请描述一种算法能够在这组数据中随机抽取k个数,使得每个数被取出来的概率相等。

1251
来自专栏云霄雨霁

加权无向图----Kruskal算法实现最小生成树

1090
来自专栏程序生活

数据挖掘作业第4章 算法设计第5章 程序实现第六章 实现结果

第4章 算法设计 4.1 实现方式1:欧式距离 实验原理如下图: ? 图 1 实验原理 4.1.1 步骤1:数据预处理 这一部分对应实验代码1的preproce...

2848
来自专栏人工智能

如何使用 scikit-learn 为机器学习准备文本数据

文本数据需要特殊处理,然后才能开始将其用于预测建模。

8898
来自专栏Bay的专栏

如何使用 scikit-learn 为机器学习准备文本数据

文本数据需要特殊处理,然后才能开始将其用于预测建模。

2215
来自专栏人人都是极客

第四课:模型的使用

上一节我们创建了模型对象,也导入了测试集,可以说实现了一个简单机器学习的apk环境和核心代码。这一节我们一起看下开发一个完整的人工智能应用程序需要哪些步骤和代码...

3245
来自专栏懒人开发

(1.6)James Stewart Calculus 5th Edition: Inverse Functions and Logarithms

前面我们有提到 e,e的对数,我们可以简写, 理解为 Natural Logarithms 自然对数

1153
来自专栏深度学习之tensorflow实战篇

tensorflow之tf.placeholder 与 tf.Variable区别对比

二者的主要区别在于 Variable:主要是用于训练变量之类的。比如我们经常使用的网络权重,偏置。 值得注意的是Variable在声明是必须赋予初始值。在训...

3244
来自专栏WindCoder

TensorFlow入门:一篇机器学习教程

TensorFlow是一个由Google创建的开源软件库,用于实现机器学习和深度学习系统。这两个名称包含一系列强大的算法,它们共享一个共同的挑战——让计算机学习...

2341
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

图像处理中任意核卷积(matlab中conv2函数)的快速实现。

     卷积其实是图像处理中最基本的操作,我们常见的一些算法比如:均值模糊、高斯模糊、锐化、Sobel、拉普拉斯、prewitt边缘检测等等一些和领域相关的算...

6758

扫码关注云+社区