狄克斯特拉算法

狄克斯特拉算法

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

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

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

执行流程

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

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

具体实现

根据图示，利用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