本文主要是介绍狄克斯特拉算法要点与python实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
使用情况
狄克斯特拉算法仅适用于有向无环图，且所有权重都是非负数。
算法步骤
- 1、找到从权值最“便宜”的节点，即可在最短时间(路程、花费等)内前往的节点；
- 2、对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销；
- 3、重复上述过程，直到对图中的每个节点都这样处理；
- 4、计算最终路径。
Python实现
# the graph
graph = {} # 定义一个散列表
# 从起点开始，每一个节点又是一个散列表，存储与其相邻节点的权值
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
# 节点a与终点fin的权值
graph["a"] = {}
graph["a"]["fin"] = 1
# 节点b与其相邻节点的权值
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
# 终点
graph["fin"] = {}# the costs table
infinity = float("inf") #定义无穷大
# 从起点开始距离各个节点的花费（相邻节点就是权重，不相邻节点未知即为无穷大）
costs = {}
costs["a"] = 6
cost这篇关于狄克斯特拉算法要点与python实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
