狄克斯特拉算法（Dijkstra’s algorithm），用于计算加权图的最小总权重。
狄克斯特拉算法适用于有向无环图，且不能计算权重为负数的图。
图
图由节点和边组成。下图中，a、b、c是节点，a->b、b->c、c->a的有向箭头是边。
相连的节点称为邻居，下图中，b是a的邻居，c是b的邻居，a是c的邻居。
非加权图
边上不带权重的图称为非加权图（unweighted graph）。
可以使用散列表（key/value）构建非加权图模型，模拟节点到邻居的映射关系：
• key为节点
• value为数组，存储节点的所有邻居节点
例如：
graph = {} #散列表（键值对）
graph["start"] = ["a","b"] # 节点a和节点b是起点start的邻居
graph["a"] = ["fin"] # 节点fin是节点a的邻居
graph["b"] = ["a","fin"] # 节点a、终点fin是节点b的邻居
广度优先搜索用于在非加权图中查找最短路径：从起点到终点经历的最少总边数。
如上图中最短路径为：起点->A->终点，或起点->B->终点，总边数为2。
而路径起点->B->A->终点，要经历3条边，不是最短路径。
加权图
边上带权重的图称为加权图（weighted graph）。
可以使用散列表（key/value）构建加权图模型，模拟节点到邻居的映射关系：
• key为节点
• value为散列表：key为节点的所有邻居，value为各个邻居的权重
例如：
graph = {} #用散列表构建图模型
graph["start"] = {} #用散列表表示起点start的所有邻居和相应的权重
graph["start"]["a"] = 6 #节点start的邻居：节点A的权重为6
graph["start"]["b"] = 2 #节点start的邻居：节点B的权重为2
graph["a"] = {} #用散列表表示节点A的所有邻居和相应的权重
graph["a"]["fin"] = 1 #节点A的邻居：终点fin的权重为1
graph["b"] = {} #用散列表表示节点B的所有邻居和相应的权重
graph["b"]["a"] = 3 #节点B的邻居：节点A的权重为3
graph["b"]["fin"] = 5 #节点B的邻居：终点fin的权重为5
graph["fin"] = {} #终点没有邻居
实现狄克斯特拉算法
1、找到起点到其它所有节点边中，权重最小的节点。
从起点无法达到的节点，权重设为无穷大
此时找到权重最小的是节点B。
这意味着，从起点到节点B，最小权重为2，不可能有更小的权重了。
代码如下
# 表示节点与权重的关系
infinity = float("inf") #表示无穷大
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
# 表示节点与父节点的关系
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
# 存储处理过的节点
processed = []
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
2、计算从起点前往该节点各个邻居的开销。
节点B的邻居：节点A、终点
【节点B】到【节点A】的权重：3
【起点】经【节点B】到【节点A】的权重：2+3=5
权重表中记录的【起点】到【节点A】的权重：6
6大于5，所以更新权重表中【节点A】的权重为5，父节点为【节点B】
【节点B】到【终点】的权重：5
【起点】经【节点B】到【终点】的权重：2+5=7
权重表中记录的【起点】到【终点】的权重：无穷大
无穷大于7，所以更新权重表中【终点】的权重为7，父节点为【节点B】
3、重复步骤1和2，直到处理过所有节点。
已处理过的节点，意味着已找到起点到该节点的最小权重，所以不用再次处理
起点和终点不处理
B节点已处理过。
除了B节点以外，权重最小的是节点A。
节点A的邻居：终点
【节点A】到【终点】的权重：1
【起点】经【节点A】到【终点】的权重：5+1=6
权重表中记录的【起点】到【终点】的权重：7
7大于6，所以更新权重表中【终点】的权重为6，父节点为【节点A】
代码如下
def dijkstras(graph, costs, parents):
node = find_lowest_cost_node(costs) #在未处理的节点中找出权重最小的节点
while node is not None: #这个while循环在所有节点都被处理过后结束
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) #找出接下来要处理的节点，并循环
4、确定最终路径
根据权重表，我们知道起点到终点的最小总权重为6
此时，找到终点的父节点：节点A
再找到节点A的父节点：节点B
节点B的父节点：起点
即找到总权重最小的路径：起点，节点B，节点A，终点
完整代码
# 建立图模型
graph = {} #用散列表构建图模型
graph["start"] = {} #用散列表表示起点start的所有邻居和相应的权重
graph["start"]["a"] = 6 #节点start的邻居：节点A的权重为6
graph["start"]["b"] = 2 #节点start的邻居：节点B的权重为2
graph["a"] = {} #用散列表表示节点A的所有邻居和相应的权重
graph["a"]["fin"] = 1 #节点A的邻居：终点fin的权重为1
graph["b"] = {} #用散列表表示节点B的所有邻居和相应的权重
graph["b"]["a"] = 3 #节点B的邻居：节点A的权重为3
graph["b"]["fin"] = 5 #节点B的邻居：终点fin的权重为5
graph["fin"] = {} #终点没有邻居
# costs
infinity = float("inf") #表示无穷大
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
# parents
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
# 存储处理过的节点
processed = []
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
def dijkstras(graph, costs, parents):
node = find_lowest_cost_node(costs) #在未处理的节点中找出开销最小的节点
while node is not None: #这个while循环在所有节点都被处理过后结束
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) #找出接下来要处理的节点，并循环
dijkstras(graph, costs, parents)
print("最小总权重：", costs["fin"])
