Dijkstra(狄克斯特拉) 算法

加权图

其中每个数字表示时间。要计算非加权图中的最短路径，可使用广度优先搜索。要计算加权图中的最短路径，可使用狄克斯特拉算法。

算法步骤

狄克斯特拉算法包含4个步骤。
(1) 找出最便宜的节点，即可在最短时间内前往的节点。
(2) 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。
(3) 重复这个过程，直到对图中的每个节点都这样做了。
(4) 计算最终路径。

算法实现：

思路草稿图：

#第一个散列表记录图结构：记录了每个节点的邻居和前往邻居的开销。f代表终点，s代表起点
graph = {}

graph['s'] = {}
graph['s']['a'] = 5
graph['s']['b'] = 2

graph['a'] = {}
graph['a']['c'] = 4
graph['a']['d'] = 2

graph['b'] = {}
graph['b']['a'] = 8
graph['b']['d'] = 7

graph['c'] = {}
graph['c']['d'] = 6
graph['c']['f'] = 3

graph['d'] = {}
graph['d']['f'] = 1

graph['f']={}

#第二个散列表：记录从起点到每个节点的开销.无法确定的计作无穷大
infinit = float('inf')
costs = {}
costs['a']= 5
costs['b'] = 2
costs['c']=infinit
costs['d']=infinit
costs['f']=infinit

#第三个散列表用于记录 每个节点的父节点
parents = {}
parents['a'] = 's'
parents['b'] = 's'
parents['f'] = None

#计算时，将不断更新 costs和parents散列表 ,并将处理过的节点记录在该数组
processed = []

#查找当前离起点最近的一个未处理的节点
def find_lowerest_node(costs):
    lowerst_cost = float('inf')
    lowerst_cost_node = None
    for node in costs:
        if costs[node] < lowerst_cost and node not in processed:
            lowerst_cost = costs[node]
            lowerst_cost_node = node 
    return lowerst_cost_node


node = find_lowerest_node(costs)

#只要还有未处理的节点，就循环处理
while node is not None:
    cost = costs[node]
    #对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。并更新父节点为该节点。
    neighbors = graph[node] 
    for n in neighbors:
        new_costs = cost + neighbors[n]
        if new_costs < costs[n]:
            costs[n] = new_costs
            parents[n] = node
    processed.append(node) 
    node = find_lowerest_node(costs)

print(costs)    

适用场景：

要计算非加权图中的最短路径，可使用广度优先搜索。要计算加权图中的最短路径，可使用狄克斯特拉算法。图还可能有环，而环类似右面这样。该算法并不能处理有环图。

负权边

负权边是指加权为负数，这样可能会导致狄克斯特拉算法失效。因此，不能将狄克斯特拉算法用于包含负权边的图。在包含负权边的图中，要找出最短路径，可使用另一种算法——贝尔曼-福德算法（Bellman-Ford algorithm）。