求解从1到6的最短路径。
python代码实现：（以A-F代表1-6）
# Dijkstra算法需要三张散列表和一个存储列表用于记录处理过的节点，如下：
processed = [] def build_graph():
"""建立图关系的散列表"""
graph = {}
graph["A"] = {}
graph["A"]["B"] = 1
graph["A"]["C"] = 12
graph["B"] = {}
graph["B"]["C"] = 9
graph["B"]["D"] = 3
graph["C"] = {}
graph["C"]["E"] = 5
graph["D"] = {}
graph["D"]["E"] = 13
graph["D"]["F"] = 15
graph["D"]["C"] = 4
graph["E"] = {}
graph["E"]["F"] = 4
graph["F"] = {}
return graph def build_costs():
"""建立开销的散列表"""
infinity = float("inf") # 无穷大
costs = {}
costs["B"] = 1
costs["C"] = 12
costs["D"] = infinity
costs["E"] = infinity
costs["F"] = infinity
return costs def build_parents():
"""建立存储父节点的散列表"""
parents = {}
parents["B"] = "A"
parents["C"] = "A"
parents["D"] = None
parents["E"] = None
parents["F"] = None
return parents # 下面是正式的算法步骤
def find_low_cost_node(costs):
"""首先要在未处理的节点找出开销最小的节点,在（开销表）中找,如果没有或者全部都已经处理过了，返回初始值None"""
lowest_cost = float("inf")
lowest_cost_node = None
for node,cost in costs.items():
if cost < lowest_cost and node not in processed:
lowest_cost = cost
lowest_cost_node = node
return lowest_cost_node def solve_shortest_route(graph,costs,parents):
"""dijkstra算法求解"""
node = find_low_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_low_cost_node(costs) # 输出结果：
print("graph:",graph)
print("costs:",costs)
print("parents:",parents) if __name__ == '__main__':
solve_shortest_route(build_graph(),build_costs(),build_parents())