这篇教程python实现狄克斯特拉算法写得很实用，希望能帮到您。
数据结构1、路由信息dictRoute = {}
dictRoute[nodeId] = {}
dictRoute[nodeId][nebrId] = distance
操作：
①根据nodeId找到该node的路由信息
②根据nebrId找到某一条路由的距离 2、节点信息dictNode = {}
dictNode[nodeId] = [shortDis, fatherId, bIsCheck]
操作：
①找到nodes中最短距离的节点
②查找节点的shortDis，根据情况更新shortDis、fatherId
③检查过的节点，更新bIsCheck 功能实现/* 找到最短距离节点的Id，已经检查的不计算在内 */
def FindShortNodeId(dictNode):
return shortNodeId /* dikstra算法流程 */
1、找到最短距离节点Id，并标记已检查过 （如果节点Id不存在，表示查找完成）
2、得到最短距离节点的距离
3、轮询最短距离节点的邻居节点
4、计算邻居节点的新距离、得到原最短距离，进行比较
5、如果新距离 < 原距离，则更新邻居节点最短距离
概括为两步：步骤1 （1）- 找到当前最短距离节点
步骤2（2~5） - 更新最短距离节点邻居节点信息 代码实现import osimport sys'''信息输入：1、节点数目、路由数目2、路由信息 3、开始节点、结束节点'''nodeNum = 0 # 节点数目routeNum = 0 # 路由数目listRoute = [] # 临时存储输入的路由信息listNodeId = []# 临时存储节点id nodeIdStart = ''nodeIdEnd = ''dictRoute = {} # 解析后的路由信息dictNode = {} # 节点信息# 输入节点数目、路由数目strInput = input()list0 = strInput.split(' ')nodeNum = int(list0[0])routeNum = int(list0[1])# 输入路由信息for index in range(routeNum): strInput = input() listRoute.append(strInput) # 输入开始节点、结束节点strInput = input()list0 = strInput.split(' ')nodeIdStart = list0[0]nodeIdEnd = list0[1]# 解析得到节点IdlistNodeId.append(nodeIdStart)listNodeId.append(nodeIdEnd)for index in listRoute: list0 = index.split(' ') nodeIdA = list0[0] nodeIdB = list0[1] if nodeIdA not in listNodeId: listNodeId.append(nodeIdA) if nodeIdB not in listNodeId: listNodeId.append(nodeIdB) # 初始化路由信息字典、节点信息字典for nodeId in listNodeId: # 节点字典信息 dictNode[nodeId] = [10000, '', False] # 最短距离、父节点、是否检查过 # 每个路由字典创建 dictRoute[nodeId] = {}dictNode[nodeIdStart][0] = 0# 初始化路由信息for index in listRoute: list0 = index.split(' ') nodeIdA = list0[0] nodeIdB = list0[1] dictRoute[nodeIdA][nodeIdB] = int(list0[2]) dictRoute[nodeIdB][nodeIdA] = int(list0[2]) # 打印输入信息def PrintInputInfo(): print('nodeNum routeNum:') print(str(nodeNum) + ' ' + str(routeNum)) print('nodeStart nodeEnd') print(nodeIdStart+' '+nodeIdEnd) print('route info:') for nodeId in dictRoute.keys(): for nebrId in dictRoute[nodeId].keys(): print(nodeId+'->'+nebrId+' = '+str(dictRoute[nodeId][nebrId])) print('node info:') for nodeId in dictNode.keys(): print(nodeId+':'+str(dictNode[nodeId][0])+' '+dictNode[nodeId][1]+' '+str(dictNode[nodeId][2]))#PrintInputInfo()'''狄克斯特拉实现'''# 找到最短距离节点iddef FindShortNodeId(dictNode): shortNodeId = '' shortDis = 10000 for nodeId in dictNode.keys(): if dictNode[nodeId][0] < shortDis and dictNode[nodeId][2] == False: shortNodeId = nodeId shortDis = dictNode[nodeId][0] return shortNodeId # 狄克斯特拉算法shortNodeId = FindShortNodeId(dictNode)while shortNodeId: if shortNodeId == nodeIdEnd: break; dictNode[shortNodeId][2] = True shortDis = dictNode[shortNodeId][0] for nebrId in dictRoute[shortNodeId].keys(): newDis = dictRoute[shortNodeId][nebrId] + shortDis if newDis < dictNode[nebrId][0]: dictNode[nebrId][0] = newDis dictNode[nebrId][1] = shortNodeId shortNodeId = FindShortNodeId(dictNode) # 打印结果listRst = []nodeId = nodeIdEndwhile nodeId: listRst.append(nodeId) nodeId = dictNode[nodeId][1]listRst.reverse()strRst = ''for nodeId in listRst: if nodeId == listRst[-1]: strRst += nodeId else: strRst += nodeId + '->'if dictNode[nodeIdEnd][1] == '': print('cant reach '+nodeIdEnd)else: print(strRst) print(dictNode[nodeIdEnd][0])测试用例及验证Case1
输入：
6 4
1 2 2
1 3 4
2 5 3
5 6 2
2 6 
输出： 
Case2
输入：
4 5
S A 6
S B 2
B A 3
A E 1
B E 5
S E 
输出： 
Case3（找不到终点）
输入：
6 6
S A 2
S B 1
A C 4
A B 1
B D 2
C D 3
S End 
输出： 
Case4
输入：
6 8
S A 5
S B 1
A C 1
A B 1
B D 5
C D 1
D End 1
C End 3
S End 
输出： 
以上就是python实现狄克斯特拉算法的详细内容，更多关于python狄克斯特拉的资料请关注51zixue.net其它相关文章！
python3 sqlite3限制条件查询的操作
python pyhs2 的安装操作 |
