代码小工蚁的#《算法图解》#学习笔记-C7狄克斯特拉算法
C7 狄克斯特拉算法Dijkstra’s algorithm
一、一些术语
带权重的图称为加权图（weighted graph），不带权重的图称为非加权图（unweighted graph）。
加权图非加权图
要计算非加权图中的最短路径，使用：广度优先搜索。
要计算加权图中的最短路径，使用：狄克斯特拉算法。
要计算包含负权边的图的最短路径，使用：贝尔曼-福德算法（Bellman-Ford algorithm）
注意：最短路径字面上是计算两点或两人之间的最短距离。
算法上的最短路径指的并不一定是物理距离，也可能是让某种度量指标最小。如花费最少，耗时最小等等。
环
无向图就是环。在无向图中，每条边都是一个环。
狄克斯特拉算法通常用于计算有向无环图（directed acyclic graph， DAG）的最短路径。
狄克斯特拉算法假设前提：对于处理过的节点，已没有前往该节点的更短路径！
如果存在负权边时，这个假设会不能成立。因此，不能将狄克斯特拉算法用于包含负权边的图。
狄克斯特拉算法背后的关键理念：找出图中“最短”的节点，并确保没有到该节点的“更短”的路径！
开销指的是从起点开始前往该节点的各边权重之和。
二、狄克斯特拉算法的实现步骤
1、找出“最短”的节点。
2、遍历计算各个该“节点的邻居”的权重，检查是否有前往该“节点的邻居”的更短路径，如果有，就更新其开销。
3、重复这个过程，直到检查完图中的每个节点。
4、计算最终路径。
处理流程
三、狄克斯特拉算法python实现
算法解题示例
#coding=utf-8
# Dijkstra's algorithm
# 找到最小开销的节点
def find_lowest_cost_node(costs):
# float('inf') 无穷大
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
# 加权图
# 图用字典表示，节点也用字典表示，键名为节点名，值为边的权重
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"] = {}
# 开销散列表
# float("inf")表示无穷大
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)
print('node=', node)
# 重复检查，直到完成所有节点
while node is not None:
# 节点的开销
cost = costs[node]
# 节点的邻居
neighbors = graph[node]
print('cost=', cost,'neighbors=', neighbors)
# 遍历节点的邻居
for n in neighbors.keys():
# 节点邻居的开销：从开始到邻居的各边权重之和
new_cost = cost + neighbors[n]
print('-- new_cost=', new_cost)
print('-- neighbor=', n, 'neighbors[n]=', neighbors[n])
# 如果找到更小开销的，就更新开销
if costs[n] > new_cost:
costs[n] = new_cost
parents[n] = node
# 已检查过的节点加入列表，防止重复检查节点
processed.append(node)
# 继续下一个节点
node = find_lowest_cost_node(costs)
# 输出检查结果
print('-' * 30)
print('processed=', processed)
print('costs=', costs)
print('parents=', parents)
参考资料：
最短路径—Dijkstra算法和Floyd算法
http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html
