单源最短路径-Dijkstra算法，是一种贪心算法，比较好理解，适合初学者。理解概念之后，代码写起来还是很容易的。
详见：http://wiki.mbalib.com/wiki/Dijkstra算法。感觉解释的很清晰，很有帮助。
使用网上很标准的一个题目作为例子：
1、起始点：1
2、目标点：5
3、顶点集合：[1,2,3,4,5,6]
4、路径集合：
{ '1,2':7,
'1,3':9,
'1,6':14,
'2,3':10,
'2,4':15,
'3,4':11,
'3,6':2,
'4,5':6,
'5,6':9 }
1、所有顶点的集合作为待处理顶点集合 undisposedPoint；
shortestDistanceFinal 记录最终最短路径（从开始点出发）；
shortestDistanceNow 记录未确定最短的路径（从开始点出发）；
pointDistanceMapNow 记录已获取的距离（从开始点出发） ；
currentPoint 记录当前处理的顶点信息（顶点名称，顶点到开始的的最短路线，顶点到开始点的最小距离）
2、将 startpoint 从 undisposedPoint 中移除
3、从 currentPoint 开始出发，获取到 undisposedPoint 中所有顶点的距离，如果获取不到，则视为无穷大。
4、比较从起点出发经过 currentPoint 到各个顶点的距离，与已记录的距离 pointDistanceMapNow中距离
的大小，更新距离信息（shortestDistanceNow，pointDistanceMapNow ）。
5、遍历 shortestDistanceNow 获取当前最小的距离，作为最短路径，获取本次最短路径顶点（这里要注意一
下，不是 currentPoint 到 undisposedPoint 中顶点的最小距离，而是 shortestDistanceNow 中记录的从
开始点开始的所有距离）。更新 shortestDistanceFinal。
6、将 本次最短路径顶点 从 pointList 中移除
7、将 本次最短路径顶点 作为下一个 currentPoint，重复步骤三，直到 最短路径顶点 = endPoint
Python3.0实现：
## 已知条件 startPoint = 1 # 开始点 endPoint = 5 # 结束点 pointList = [6,5,4,3,2,1] # 顶点集合 pointDistanceMap = { # 已知距离集合 '1,2':7, '1,3':9, '1,6':14, '2,3':10, '2,4':15, '3,4':11, '3,6':2, '4,5':6, '5,6':9 } # 求解过程 # 从距离集合中获取距离信息 # [点一,点二,要查找的距离集合,是否可以反转] # [线路,是否可达,距离] def getDistance(p1,p2,distanceMap,canReverse) : path1 = str(p1) + ',' + str(p2) distance1 = distanceMap.get(path1,False) res1 = [path1,True,distance1] if canReverse : path2 = str(p2) + ',' + str(p1) distance2 = distanceMap.get(path2,False) res2 = [path2,True,distance2] if distance2 : if distance1 : if distance2 < distance1 : return res2 else : return res1 else : return res2 if distance1 : return res1 else : return [path1,False,'∞'] # 画个符号吧，好看 undisposedPoint = pointList # 未寻得最小路径的点集合 shortestDistanceFinal = {} # 从开始点出发，最终线路 shortestDistanceNow = {} # 从开始点出发，未确定线路 pointDistanceMapNow = {} # 从开始点出发，所有当前已知距离 currentPoint = (1,'1',0) # 当前点：[当前点,线路,距离] undisposedPoint.remove(startPoint) while len(undisposedPoint) != 0 : print('当初处理顶点信息：',currentPoint,end='\n\n') for i in undisposedPoint : currentDistance = getDistance(currentPoint[0],i,pointDistanceMap,True) print('当前顶点到未处理点距离信息 : ',currentDistance) # 如果线路可达 if currentDistance[1] : knownDistance = getDistance(startPoint,i,pointDistanceMapNow,False) print('历史当前顶点到未处理点距离 : ',knownDistance) # 如果已知线路为空或者大于新取得的线路，更新已知线路信息 if not knownDistance[1] or \ currentPoint[2] + currentDistance[2] < knownDistance[2] : shortestDistanceNow[knownDistance[0]] = [ i , currentPoint[1] + ',' + str(i) ,\ currentPoint[2] + currentDistance[2] ] pointDistanceMapNow[knownDistance[0]] = currentPoint[2] + currentDistance[2] print('更新后的已知距离 : ',pointDistanceMapNow) print('更新后的已知线路 : ',shortestDistanceNow,end='\n\n') # 遍历未确定线路，确定本次最小线路。将最小距离从未确定线路中移除，并添加到最终线路中 shortestPath = '' shortestDistance = float('inf') for key in shortestDistanceNow : if shortestDistanceNow[key][2] < shortestDistance : shortestPath = key shortestDistance = shortestDistanceNow[key][2] currentPoint = [ shortestDistanceNow[shortestPath][0] , \ shortestDistanceNow[shortestPath][1] , \ shortestDistanceNow[shortestPath][2] ] shortestDistanceFinal[shortestPath] = [ shortestDistanceNow[shortestPath][1], \ shortestDistanceNow[shortestPath][2] ] # 从未处理顶点中移除本次确定最小距离的点 undisposedPoint.remove(shortestDistanceNow[shortestPath][0]) del shortestDistanceNow[shortestPath] # del pointDistanceMapNow[shortestPath] # 方便测试，不移除了 print('本次的最小距离：',currentPoint) print('最终的最小距离：',shortestDistanceFinal) print('未确定线路信息：',shortestDistanceNow) print('未处理的顶点集：',undisposedPoint,end='\n\n\n') if currentPoint[0] == endPoint : print('从 {0} 到 {1} 最小距离为：{2}'.format(startPoint,endPoint, \ shortestDistanceFinal[str(startPoint)+','+str(endPoint)])) break else : print('目标不可达！')
打印日志信息如下：
当初处理顶点信息：(1, '1', 0)
当前顶点到未处理点距离信息: ['1,6', True, 14]
历史当前顶点到未处理点距离 : ['1,6',False, '∞']
当前顶点到未处理点距离信息 : ['1,5',False, '∞']
当前顶点到未处理点距离信息 : ['1,4',False, '∞']
当前顶点到未处理点距离信息: ['1,3', True, 9]
历史当前顶点到未处理点距离 : ['1,3',False, '∞']
当前顶点到未处理点距离信息: ['1,2', True, 7]
历史当前顶点到未处理点距离 : ['1,2',False, '∞']
更新后的已知距离: {'1,3': 9, '1,2': 7, '1,6': 14}
更新后的已知线路: {'1,3': [3, '1,3', 9], '1,2': [2,'1,2', 7], '1,6': [6, '1,6', 14]}
本次的最小距离：[2, '1,2', 7]
最终的最小距离：{'1,2': ['1,2', 7]}
未确定线路信息：{'1,3': [3, '1,3', 9], '1,6': [6, '1,6', 14]}
未处理的顶点集：[6, 5, 4, 3]
当初处理顶点信息：[2, '1,2', 7]
当前顶点到未处理点距离信息 : ['2,6',False, '∞']
当前顶点到未处理点距离信息 : ['2,5',False, '∞']
当前顶点到未处理点距离信息: ['2,4', True, 15]
历史当前顶点到未处理点距离 : ['1,4',False, '∞']
当前顶点到未处理点距离信息: ['2,3', True, 10]
历史当前顶点到未处理点距离: ['1,3', True, 9]
更新后的已知距离: {'1,4': 22, '1,3': 9, '1,2': 7, '1,6':14}
更新后的已知线路: {'1,4': [4, '1,2,4', 22], '1,3': [3,'1,3', 9], '1,6': [6, '1,6', 14]}
本次的最小距离：[3, '1,3', 9]
最终的最小距离：{'1,3': ['1,3', 9], '1,2': ['1,2', 7]}
未确定线路信息：{'1,4': [4, '1,2,4', 22], '1,6': [6, '1,6', 14]}
未处理的顶点集：[6, 5, 4]
当初处理顶点信息：[3, '1,3', 9]
当前顶点到未处理点距离信息: ['3,6', True, 2]
历史当前顶点到未处理点距离: ['1,6', True, 14]
当前顶点到未处理点距离信息 : ['3,5',False, '∞']
当前顶点到未处理点距离信息: ['3,4', True, 11]
历史当前顶点到未处理点距离: ['1,4', True, 22]
更新后的已知距离: {'1,4': 20, '1,3': 9, '1,2': 7, '1,6':11}
更新后的已知线路: {'1,4': [4, '1,3,4', 20], '1,6': [6,'1,3,6', 11]}
本次的最小距离：[6, '1,3,6', 11]
最终的最小距离：{'1,3': ['1,3', 9], '1,2': ['1,2', 7], '1,6': ['1,3,6', 11]}
未确定线路信息：{'1,4': [4, '1,3,4', 20]}
未处理的顶点集：[5, 4]
当初处理顶点信息：[6, '1,3,6', 11]
当前顶点到未处理点距离信息: ['5,6', True, 9]
历史当前顶点到未处理点距离 : ['1,5',False, '∞']
当前顶点到未处理点距离信息 : ['6,4',False, '∞']
更新后的已知距离: {'1,4': 20, '1,3': 9, '1,5': 20,'1,2': 7, '1,6': 11}
更新后的已知线路: {'1,4': [4, '1,3,4', 20], '1,5': [5,'1,3,6,5', 20]}
本次的最小距离：[4, '1,3,4', 20]
最终的最小距离：{'1,4': ['1,3,4', 20], '1,3': ['1,3', 9], '1,2': ['1,2', 7], '1,6': ['1,3,6',11]}
未确定线路信息：{'1,5': [5, '1,3,6,5', 20]}
未处理的顶点集：[5]
当初处理顶点信息：[4, '1,3,4', 20]
当前顶点到未处理点距离信息: ['4,5', True, 6]
历史当前顶点到未处理点距离: ['1,5', True, 20]
更新后的已知距离: {'1,4': 20, '1,3': 9, '1,5': 20,'1,2': 7, '1,6': 11}
更新后的已知线路: {'1,5': [5, '1,3,6,5', 20]}
本次的最小距离：[5, '1,3,6,5', 20]
最终的最小距离：{'1,4': ['1,3,4', 20], '1,3': ['1,3', 9], '1,5': ['1,3,6,5', 20], '1,2':['1,2', 7], '1,6': ['1,3,6', 11]}
未确定线路信息：{}
未处理的顶点集：[]
从 1 到5 最小距离为：['1,3,6,5', 20]
1、
startPoint=1 #开始点
endPoint=6 #结束点
pointList=[6,5,4,3,2,1] #顶点集合
pointDistanceMap={ #已知距离集合
'1,2':1,
'1,3':1,
'2,4':3,
'4,6':3,
'3,5':1,
'5,6':1 }
结果：从 1 到 6 最小距离为：['1,3,5,6', 3]
2、
startPoint=1 #开始点
endPoint=6 #结束点
pointList=[9,8,7,6,5,4,3,2,1] #顶点集合
pointDistanceMap={ #已知距离集合
'1,2':1,
'1,7':2,
'2,3':2,
'2,4':3,
'4,5':4,
'5,6':1,
'6,8':9,
'7,8':1,
'7,9':1}
3、
startPoint=1 #开始点
endPoint=6 #结束点
pointList=[6,5,4,3,2,1] #顶点集合
pointDistanceMap={ #已知距离集合
'1,2':3,
'1,4':3,
'2,3':1,
'2,4':2,
'2,6':6,
'3,4':1,
'3,6':5,
'4,5':2,
'5,6':4}
结果：从1 到 6 最小距离为：['1,2,6', 9]
PS：在代码里打印中文日志，对理解运行还是很有帮助的。
