Linux|系统管理|WEB开发

单源最短路径算法中dijtstra算法是最经典的了。下面是python实现方式
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

#!/usr/bin/env python
“”"
Shortest Path Dijkstra Algorithm
author: mlsx mlsx.xplore@gmail.com
“”"

if __name__==”__main__”:
I=9999 #无穷大
N=20 #城市顶点的个数
true=1
false=0
cost = [
[0,3,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I,I,I],
[3,0,5,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I,I,I],
[I,5,0,4,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I],
[I,I,4,0,2,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I],
[I,I,I,2,0,I,I,I,I,7,I,I,I,I,I,I,I,I,I,I],
[1,I,I,I,I,0,1,I,I,I,2,I,I,I,I,I,I,I,I,I],
[I,6,I,I,I,1,0,6,I,I,I,7,I,I,I,I,I,I,I,I],
[I,I,1,I,I,I,6,0,2,I,I,I,3,I,I,I,I,I,I,I],
[I,I,I,6,I,I,I,2,0,8,I,I,I,4,I,I,I,I,I,I],
[I,I,I,I,7,I,I,I,8,0,I,I,I,I,5,I,I,I,I,I],
[I,I,I,I,I,2,I,I,I,I,0,4,I,I,I,3,I,I,I,I],
[I,I,I,I,I,I,7,I,I,I,4,0,3,I,I,I,4,I,I,I],
[I,I,I,I,I,I,I,3,I,I,I,3,0,3,I,I,I,5,I,I],
[I,I,I,I,I,I,I,I,4,I,I,I,3,0,7,I,I,I,2,I],
[I,I,I,I,I,I,I,I,I,5,I,I,I,7,0,I,I,I,I,3],
[I,I,I,I,I,I,I,I,I,I,3,I,I,I,I,0,5,I,I,I],
[I,I,I,I,I,I,I,I,I,I,I,4,I,I,I,5,0,8,I,I],
[I,I,I,I,I,I,I,I,I,I,I,I,5,I,I,I,8,0,6,I],
[I,I,I,I,I,I,I,I,I,I,I,I,I,2,I,I,I,6,0,4],
[I,I,I,I,I,I,I,I,I,I,I,I,I,I,3,I,I,I,4,0]]
dist=[0]*N #”"” 存储当前最短路径长度 “”"
v0 = 0
final=[0]*N
for x in range(N):
#”"” 初始化最短路径长度数据，所有数据都不是最终数据 “”"
final[x]=false
dist[x]=cost[v0][x]
final[v0]= true
for i in range(N-1):
min=I #”"” 初始最短长度无穷大 “”"
#”"” 寻找最短的边 “”"
for w in range(N):
if ((not final[w]) and (dist[w]< min)):
min=dist[w]
v=w
final[v]=true # """ 加入新边 """

for w in range(N):
if ((not final[w]) and (dist[v] + cost[v][w] < dist[w])):
dist[w]=dist[v] + cost[v][w] #""" 更新 dist[] 数据 """

for i in range(N):
print "%c->%c: %2d ” % (v0 + 65, i + 65, dist) #”"” 显示到监视器 “”"