算法学习笔记–狄克斯特拉算法

主要内容

加权图：提高或降低某些边的权重介绍狄克斯特拉算法，能找出加权图中前往X的最短路径图中的环会导致狄克斯特拉算法不管用，如果有负权重也不适用 如果要处理负权重的图，可以使用贝尔曼-福德算法

狄克斯特算法的四个步骤

找出最便宜的节点，即可在最短时间内到达的节点对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。重复这个过程，直到对图中的每个节点都这样做了。就是对每个节点都做，做完一个扔掉一个。

计算最终路径。

对于狄克斯特算法计算的时候画一个表格，三列分别为父节点，节点和开销，最短的路径是多少看最后的开销，最短的路径沿着父节点回溯。

几个定义

边带权重的图称为加权图，不带权重的称为非加权图。计算非加权图的最短路径使用广度优先搜索。

绕环的路径不可能是最短的路径。

绕环图就等于无向图

狄克斯特只适用与有向无环图

实现

需要三个散列表，并且graph图列表是嵌套的散列表 1. graph散列表 2. costs开销散列表 3. parents父节点散列表

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 if __name__ == '__main__': 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 processed = [] 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 costs[n] > new_cost: costs[n] = new_cost parents[n] = node processed.append(node) node = find_lowest_cost_node(costs) print costs['fin']