Dijkstra算法思想及实现

算法思想

Dijkstra算法包含四个步骤：

找出“最便宜”的节点，即可在最短时间内到达的节点。
更新该节点的邻居的开销。
重复上述过程，直到对图中的每个节点都这样操作了。
计算最终路径。

注意：Dijkstra算法只适用于正加权有向无环图(directed acyclic graph, DAG)

Dijkstraa算法关键理念：找出图中最便宜的节点，并确保没有到该节点的最便宜的路径。

算法实现

如下图的Graph:

python算法实现如下：

'''
@Author: Angus Cai
@Date: 2019-05-13 15:06:14
@LastEditors: Angus Cai
@LastEditTime: 2019-05-17 09:25:27
@Description: Dijkstra算法实现
'''

graph = { 'start': {'A':3, 'B':1},
          'A': {'B':4, 'C':6},
          'B': {'C':5, 'D':7},
          'C': {'D':9, 'end':5},
          'D': {'end':8},
          'end': {}}

infinity = float("inf")
costs = {}
costs['A'] = 3
costs['B'] = 2
costs['C'] = infinity
costs['D'] = infinity
costs['end'] = infinity

parents = {}
parents['A'] = 'start'
parents['B'] = 'start'
parents['C'] = None
parents['D'] = None
parents['end'] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

node = find_lowest_cost_node(costs)

while node is not None:
    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)
print(parents)

path = []
node = parents['end']
while node != 'start':
    path.append(node)
    node = parents[node]
i = len(path)-1
final_path = ''
while i>=0:
    final_path = final_path+str(path[i])+'->'
    i -= 1
print('start->'+final_path+'end')

########################## output ############################
# {'A': 3, 'B': 2, 'C': 7, 'D': 9, 'end': 12}
# {'A': 'start', 'B': 'start', 'C': 'B', 'D': 'B', 'end': 'C'}
# start->B->C->end