狄克斯特拉算法

狄克斯特拉算法

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

image.png

在上面的图中,我们的目的是想要找到起点终点 之间最快的路径,每个边之间都是相应的权重的,如果我们想要做到,那么我们就可以使用狄克斯特拉算法 来实现

但是,需要注意的是,狄克斯特拉算法不能解决负权 的问题,如果想要实现负权的具体问题实现,那么可以使用贝尔曼—福德 算法

执行流程

  • 找出最便宜的节点,即可在最短时间内前往的节点
  • 对于该节点的邻居,检查是否有前往它们的更短路径,如果有,就更新其开销
  • 重复这个过程,直到对图中的每个节点都这样做了
  • 计算最终路径

除了使用散列表来正确的存储图外,我们还需要开销花费的散列表和每个节点的父节点,我们的目标就是不断的去更新这两个表格,最终计算出最后的结果

具体实现

根据图示,利用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
喜欢就支持以下吧
点赞0
分享
评论 抢沙发
四曲的头像-四曲博客

昵称

取消
昵称表情代码图片