从起点到终点的最短路径。

算法逻辑：

1）找出最便宜的节点，即可在最短时间内前往的节点

2）对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销

3）如果有邻居的开销被更新，同时更新其父节点

4）将该节点标记为处理过

5）重复以上过程，直到对图中的每个节点都这样做了。

6）计算出最终路径

python源码部分

dijkstra.py

# -*- coding: utf-8 -*

# 迪克斯特拉算法

#import dijkstra

#graph={}

#graph=dijkstra.create_data_1()

#costs={}

#costs=dijkstra.create_data2()

#parents={}

#parents=dijkstra.create_data3()

#processed=[]

#dijkstra.results(graph,costs,parents,processed)

#print costs

#{'a': 5, 'b': 2, 'fin': 6}

#print parents

#{'a': 'b', 'b': 'start', 'fin': 'a'}

def results(graph,costs,parents,processed):

  node=find_lowest_cost_node(costs,processed)

  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,processed)

#存储邻居到散列表

def create_data_1():

 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"]={}

 return graph

#开销表

def create_data2():

 costs={}

 costs["a"]=6

 costs["b"]=2

 costs["fin"]=10000

 return costs

#存储父节点的散列表

def create_data3():

 parents={}

 parents["a"]="start"

 parents["b"]="start"

 parents["fin"]=None

 return parents

#processed = []

#找出最低开销的节点

def find_lowest_cost_node(costs,processed):

 lowest_cost=10000

 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