狄克斯特拉算法实现

最近学习《算法图解》，记录一下自己默写的狄克斯特拉算法，该算法用Python书写。

graph = {}
infinity = float('inf')

graph['start'] = {}
graph['start']['a'] = 5
graph['start']['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']['fin'] = 3
graph['c']['d'] = 6

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

graph['fin'] = {}

costs = {}
costs['a'] = 5
costs['b'] = 2
costs['c'] = infinity
costs['d'] = infinity
costs['fin'] = infinity

parents = {}
parents['a'] = 'start'
parents['b'] = 'start'
parents['c'] = None
parents['d'] = None
parents['fin'] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = infinity
    lowest_cost_node = None
    for node in costs:
        if costs[node] < lowest_cost and node not in processed:
            lowest_cost = costs[node]
            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(parents)

arr = []

key = parents['fin']

while key != 'start':
    arr.append(key)
    key = parents[key]

arr.reverse()
print('最短路径为：start',end='')
for i in arr:
    print('-'+i,end='')
print('-fin')
print('最短路径的花费为：' + str(costs['fin']))

狄克斯特拉算法只可用于获取有向无环图（加权图）的最短路径，且图内不能有负权边。

图内有负权边需要使用贝尔曼-福德算法，无权图则用广度优先搜索（Breadth First Search）算法可得出最短路径。