算法图解阅读笔记——第四曲（狄克斯特拉算法和贪婪算法）

程序员文章站 2022-06-04 16:05:37

...

目录结构

第7章狄克斯特拉算法

第8章贪婪算法

狄克斯特拉算法

算法图解阅读笔记——第四曲（狄克斯特拉算法和贪婪算法）

图A是使用广度优先搜索算法计算最短路径的图结构（非加权图）

——在非加权图中计算最短路径，可使用广度优先搜索
图B是使用狄克斯特拉算法计算最短路径的图结构（加权图）

——在加权图中计算最短路径，可使用狄克斯特拉算法

什么是狄克斯特拉算法

狄克斯特拉算法是一种在加权图算法，目的是为了解决加权图中最短路径的问题，只适用于有向无环图，而且图中的权值不能为负。

使用狄克斯特拉算法

算法步骤：
1. 找出"最便宜"的节点，即可在最短时间内到达的节点。
2. 更新该节点的邻居开销（从起点到该节点各邻居的开销）。
3. 重复①②这个过程，直至对图中的每个节点都这样做了。
4. 计算得到最终路径

实现狄克斯特拉算法

使用下图来实现狄克斯特拉算法

def find_lowest_cost_node(costs_dict):
    """
        找开销最小的路径
    """
    lowest_cost = float('inf')
    lowest_cost_node = None
    for node in costs_dict:
        cost = costs_dict[node]
        if cost < lowest_cost and node not in processed_node:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node


graph = {}    # 创建图

graph['start'] = {}
graph['start']['a'] = 6
graph['start']['b'] = 2

graph['a'] = {}
graph['a']['end'] = 1

graph['b'] = {}
graph['b']['a'] = 3
graph['b']['end'] = 5

graph['end'] = {}

print('初始化graph：', graph)

infinity = float('inf')

costs = {}  # 开销图
costs['a'] = 6
costs['b'] = 2
costs['end'] = infinity
print('初始化costs：', costs)

parents = {}   # 父节点图
parents['a'] = 'start'
parents['b'] = 'start'
parents['end'] = None
print('初始化parents：', parents)

processed_node = []

node = find_lowest_cost_node(costs)
while node is not None:
    cost = costs[node]
    neighbors = graph[node]

    for neighbor in neighbors.keys():
        new_cost = cost + neighbors[neighbor]
        if costs[neighbor] > new_cost:
            costs[neighbor] = new_cost
            parents[neighbor] = node

    processed_node.append(node)
    node = find_lowest_cost_node(costs)


print('狄克斯特拉算法计算costs：', costs)
print('狄克斯特拉算法计算parents：', parents)

# Out
# 初始化graph： {'start': {'a': 6, 'b': 2}, 'a': {'end': 1}, 'b': {'a': 3, 'end': 5}, 'end': {}}
# 初始化costs： {'a': 6, 'b': 2, 'end': inf}
# 初始化parents： {'a': 'start', 'b': 'start', 'end': None}
# 狄克斯特拉算法计算costs： {'a': 5, 'b': 2, 'end': 6}
# 狄克斯特拉算法计算parents： {'a': 'b', 'b': 'start', 'end': 'a'}

# 显示最终路径
start_end_dic = dict(zip(parents.values(), parents.keys()))  # 字典key，value互换

next_node = None
for i in range(len(start_end_dic)-1):
    start_node = 'start'

    if i == 0:
        print('最终路径：', start_node, end='——>')
        next_node = start_end_dic[start_node]
    print(next_node, end='——>')

    next_node = start_end_dic[next_node]
print('end')

# Out
# start——>b——>a——>end