狄克斯特拉算法
在广度优先搜索算法当中,我们可以找到在图当中段数最少的路径,那如果我想找到最快的路径该怎么办呢?

在上面的图中,我们的目的是想要找到起点 和终点 之间最快的路径,每个边之间都是相应的权重的,如果我们想要做到,那么我们就可以使用狄克斯特拉算法 来实现
但是,需要注意的是,狄克斯特拉算法不能解决负权 的问题,如果想要实现负权的具体问题实现,那么可以使用贝尔曼—福德 算法
执行流程
- 找出最便宜的节点,即可在最短时间内前往的节点
- 对于该节点的邻居,检查是否有前往它们的更短路径,如果有,就更新其开销
- 重复这个过程,直到对图中的每个节点都这样做了
- 计算最终路径
除了使用散列表来正确的存储图外,我们还需要开销花费的散列表和每个节点的父节点,我们的目标就是不断的去更新这两个表格,最终计算出最后的结果
具体实现
根据图示,利用Python字典的方式建立图关系
graph['start'] = {'a':6,'b':2}
graph['a'] = {'fin':1}
graph['b'] = {'a':3,'fin':5}
graph['fin'] ={}
建立开销表,由于我们是从start开始,没有办法确定到inf的开销,索引将fin设置为无穷大,但是我们知道到a节点和b节点的开销,
infinity = float("inf") #设置无穷大变量
costs = {}
costs['a'] = 6
costs['b'] = 2
costs['fin'] = infinity
建立每个节点的父节点表,对于fin来说,我们不知道fin在那个位置,因此,fin的父节点是None
parents = {}
parents['a'] = 'start'
parents['b'] = 'start'
parents['fin'] = None
具体的实现流程如下:
processed = [] #用于存储,那个节点已经遍历过
node = find_lowest_cost_node(costs) #找出开销最小的节点
while node:
cost = costs[node] #获取节点的开销
neighbors = graph[node] #获取节点的邻居节点
for n in neighbors.keys():
new_cost = cost + neighbors[n] #计算出最近的开销
if new_cost < costs[n]: #如果新的开销比较小
costs[n] = new_cost #则更新开销表
parents[n] = node #找到新的最短路径,更新父节点
processed.append(node) #标记已经遍历过
node = find_lowest_cost_node(costs)
print(costs['fin'])
对于函数find_lowest_cost_node()来说,找出在costs表中花费的最小开销的节点即可
def find_lowest_cost_node(costs):
lowest_cost = infinity #将最小开销设置为无穷大
lowest_cost_node = None
for n in costs:
cost = costs[n]
if lowest_cost > cost and ( n not in processed):
lowest_cost = cost
lowest_cost_node = n
return lowest_cost_node
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END
暂无评论内容