Dijkstras

总结Dijkstras算法
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
首先初始化，将所有结点的距离设为无穷大。所有结点标记为un-visited。然后将起点的距离值设为0。 然后进行如下操作：

1. 找出unvisited结点中，距离值最小的结点min_v。
2. 遍历所有与min_v联通的结点，并更新这些结点的distance值。
3. 把min_v设为visited。
4. 重复上述操作直至没有unvisited的结点了 (len(visited) == n)（这个终止条件一直想不清楚，请注意！）

import heapq
import sys
def addEdge(graph, start, end, distance):
  graph[start].append([distance, end])
  graph[end].append([distance, start])

def dijkstras(graph, start):
  n = len(graph)
  distance = []
  for i in range(n): distance.append([sys.maxint, i])
  distance[start][0] = 0
  res = [0]*n
  visited = []
  while ( len(visited) != n ):
    tmp = distance[:]
    heapq.heapify(tmp)
    tmpp = heapq.heappop(tmp)
    min_v, min_d = tmpp[1], tmpp[0]
    for edge in graph[min_v]:
      if ( edge[1] in visited ): continue
      distance[edge[1]][0] = min(distance[edge[1]][0], min_d + edge[0])
    res[min_v] = min_d
    distance[min_v][0] = sys.maxint
    visited.append(min_v)
  print res

n = 9
graph = []
for i in range(n):
  tmp = []
  graph.append(tmp)

addEdge(graph, 0, 1, 4)
addEdge(graph, 0, 7, 8)
addEdge(graph, 1, 2, 8)
addEdge(graph, 1, 7, 11)
addEdge(graph, 2, 3, 7)
addEdge(graph, 2, 8, 2)
addEdge(graph, 2, 5, 4)
addEdge(graph, 3, 4, 9)
addEdge(graph, 3, 5, 14)
addEdge(graph, 4, 5, 10)
addEdge(graph, 5, 6, 2)
addEdge(graph, 6, 7, 1)
addEdge(graph, 6, 8, 6)
addEdge(graph, 7, 8, 7)

dijkstras(graph, 0)

Dijkstras算法的正确性：
先来看这三条属性：

• 属性1: visited中任意m的点的的路径长度D[m]就是其最短路径。
• 属性2: 对于unvisited中的任意结点n，其估值路径D_est[n]是其只通过visited中结点的最短路径。
• 属性3: unvisited中估值最小的点n，D_est[n]的值就是其最短路径。