Dijkstra:
#Dijkstra算法只能解决有向无负权图单源最短路径#其基本思想是每次找出距离已经访问过的集合最短边连接的点，以该点为基准进行松弛
#Dijkstra算法只能解决有向无负权图单源最短路径 #其基本思想是每次找出距离已经访问过的集合最短边连接的点，以该点为基准进行松弛 import time begin=time.clock() juzhen=[ [0,4,2,5,999,999,999,999,999,999], [999,0,999,999,7,5,999,999,999,999], [999,999,0,999,999,9,999,999,999,999], [999,999,999,0,2,999,7,999,999,999], [999,999,999,999,0,999,999,4,999,999], [999,999,999,999,999,0,999,999,999,6], [999,999,999,999,999,999,0,999,3,999], [999,999,999,999,999,999,999,0,999,7], [999,999,999,999,999,999,999,999,0,8], [999,999,999,999,999,999,999,999,999,0] ] distance=[0 for i in range(10)]#共有十个顶点，表示每个顶点到源点的距离 used=[0 for i in range(10)]#记录是否已经求得最短路径(将所有的初始化为0) used[0]=1#本身已经求得最短路径0 for i in range(10): #初始化原始距离 distance[i]=juzhen[0][i] for i in range(1,10): #每次找一个距离“源点”最近的点 k=1 min=999 #999代表无穷大，用其代表没路可走 for j in range(10): #每次找到距离以标记集合中的最短的点 if(used[j]==0 and distance[j]<min): min=distance[j] #找到该点，标记它 k=j used[k]=1 for w in range(10): #以找到的点为中心，“松弛其他点到源点的最短距离” if(used[w]==0 and min+juzhen[k][w]<distance[w]): distance[w]=min+juzhen[k][w] end=time.clock() for i in range(10): print(distance[i]) print(end-begin)Bellman-Ford算法：
#Ford算法可以用于解决有向图无向图以及负边权图 #其基本思想是首先将除了源节点之外到源节点的距离设置为无穷大，本身设置成0，依次访问n-1个点，以该点为基准进行松弛 import time begin=time.clock() juzhen=[ [0,4,2,5,999,999,999,999,999,999], [999,0,999,999,7,5,999,999,999,999], [999,999,0,999,999,9,999,999,999,999], [999,999,999,0,2,999,7,999,999,999], [999,999,999,999,0,999,999,4,999,999], [999,999,999,999,999,0,999,999,999,6], [999,999,999,999,999,999,0,999,3,999], [999,999,999,999,999,999,999,0,999,7], [999,999,999,999,999,999,999,999,0,8], [999,999,999,999,999,999,999,999,999,0] ] isornotfuquanhuilu=0 distance=[999 for i in range(10)] distance[0]=0 for i in range(10): for j in range(10): if(distance[i]!=999 and distance[i]+juzhen[i][j]<distance[j]): distance[j]=distance[i]+juzhen[i][j] for i in range(10): for j in range(10): if(distance[i]!=999 and distance[i]+juzhen[i][j]<distance[j]): isornotfuquanhuilu=1 end=time.clock() if isornotfuquanhuilu==1: print("存在负权回路") else: for i in range(10): print(distance[i]) print(end-begin)spfa算法：（分支界限法求最短路径）
""" Spfa算法是Bellman-Ford算法的优化版本 只有那些在前一遍松弛中改变了距离估计值的点，才可能引起他们的邻接点的距离估计值的改变。 """ import time begin=time.clock() juzhen=[ [0,4,2,5,999,999,999,999,999,999], [999,0,999,999,7,5,999,999,999,999], [999,999,0,999,999,9,999,999,999,999], [999,999,999,0,2,999,7,999,999,999], [999,999,999,999,0,999,999,4,999,999], [999,999,999,999,999,0,999,999,999,6], [999,999,999,999,999,999,0,999,3,999], [999,999,999,999,999,999,999,0,999,7], [999,999,999,999,999,999,999,999,0,8], [999,999,999,999,999,999,999,999,999,0] ] distance=[999 for i in range(10)] used=[0 for i in range(10)] q=[0 for i in range(1000)] distance[0]=0 used[0]=1 head=0 tail=1 q[tail]=0 while(head<tail): head+=1 v=q[head] used[v]=0 for i in range(10): if(distance[i]>distance[v]+juzhen[v][i]): distance[i]=distance[v]+juzhen[v][i] if(used[i]==0): tail+=1 q[tail]=i used[i]=1 end=time.clock() for i in range(10): print(distance[i]) print(end-begin)