狄克斯特拉算法

寻找起点到终点的最近路

1、需要准备三个散列

## 节点
graph = {}
graph['start'] = {}
graph['start']['a'] = 6
graph['start']['b'] = 2
graph['a'] = {}
graph['a']['fin'] = 1
graph['b'] = {}
graph['b']['a'] = 3
graph['b']['fin'] = 5
graph['fin'] = {}

## 开销散列
infinity = float('inf')
costs = {}
costs['a'] = 6
costs['b'] = 2
costs['fin'] = infinity

## 父节点散列
parents = {}
parents['a'] = 'start'
parents['b'] = 'start'
parents['fin'] = None

2、寻找开销最小节点

## 找到开销最小节点
def find_lowet_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

3、算法简单实现

## 算法实现
processed = []
node = find_lowet_cost_node(costs)
while node is not None:
    cost = costs[node]
    neighbors = graph[node]
    for nb in neighbors.keys():
        new_cost = cost + neighbors[nb]
        if costs[nb] > new_cost: # 如果经当前节点前往该邻居更近
            costs[nb] = new_cost # 就将该最近的值赋值给开销散列中
            parents[nb] = node   # 将该邻居的父节点设置为当前节点
    processed.append(node)
    node = find_lowet_cost_node(costs)

print(costs)  # {'a': 5, 'b': 2, 'fin': 6}

因此到终点最近距离是 6 ， 到A的最近距离是5 ，到B的最近距离是2。
该算法可以用在社交网络中通过最亲密的朋友线去寻找想认识的人，不过散列会非常的大