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

本文主要是介绍算法学习笔记--狄克斯特拉算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

主要内容

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

狄克斯特算法的四个步骤

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

4. 计算最终路径。

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

几个定义

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

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

绕环图就等于无向图

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

实现

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

def find_lowest_cost_node(costs):lowest_cost = float('inf')lowest_cost_node = Nonefor node in costs:cost = costs[node]if cost < lowest_cost and node not in processed:lowest_cost = cost lowest_cost_node = nodereturn lowest_cost_nodeif __name__ == '__main__':graph = {}graph['start'] = {}graph['start']['a'] = 6graph['start']['b'] = 2graph['a'] = {}graph['a']['fin'] = 1graph['b'] = {}graph['b']['a'] = 3graph['b']['fin'] = 5graph['fin'] = {}infinity = float("inf")costs = {}costs['a'] = 6costs['b'] = 2costs["fin"] = infinityparents = {}parents["a"] = "start"parents["b"] = "start"parents["fin"] = Noneprocessed = []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_costparents[n] = nodeprocessed.append(node)node = find_lowest_cost_node(costs)print costs['fin']

这篇关于算法学习笔记--狄克斯特拉算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---