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

相关文章

来自专栏懒人开发

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

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

1013
来自专栏程序生活

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

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

2758
来自专栏Deep Learning 笔记

CNN+MNIST+INPUT_DATA数字识别

TALK IS CHEAP,SHOW ME THE CODE,先从MNIST数据集下载脚本Input_data开始

1953
来自专栏xingoo, 一个梦想做发明家的程序员

动态规划基本要素

动态规划性质: 1  最优子结构性质  2 子问题重叠性质 ----->该问题可用动态规划算法求解的基本要素 1 最优子结构 当问题的最优解包含了其子问题的最优...

19110
来自专栏人人都是极客

第四课:模型的使用

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

3195
来自专栏逍遥剑客的游戏开发

基于法线的边缘检测

1523
来自专栏鸿的学习笔记

写给开发者的机器学习指南(十三)

在我们实际使用支持向量机(SVM)之前,我先简要介绍一下SVM是什么。 基本SVM是一个二元分类器,它通过选取代表数据点之间最大间隔的超平面将数据集分成2部分。...

451
来自专栏xingoo, 一个梦想做发明家的程序员

布线问题-分支限界法

问题描述:   印刷电路板不限区域划分成n*m个方格阵列。如下图所示 ?   精确的电路布线问题要求确定连接方格a的中点,到连接方格b的中点的最短布线方案。  ...

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

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

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

5228
来自专栏小樱的经验随笔

POJ 3154 Graveyard【多解,数论,贪心】

Graveyard Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 170...

3234

扫码关注云+社区