python实现狄克斯特拉算法

dictRoute = {}dictRoute[nodeId] = {}dictRoute[nodeId][nebrId] = distance操作：①根据nodeId找到该node的路由信息②根据nebrId找到某一条路由的距离

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 41 2 21 3 42 5 35 6 22 6

输出：

Case2输入：4 5S A 6S B 2B A 3A E 1B E 5S E

输出：

Case3（找不到终点）输入：6 6S A 2S B 1A C 4A B 1B D 2C D 3S End

输出：

Case4输入：6 8S A 5S B 1A C 1A B 1B D 5C D 1D End 1C End 3S End

输出：

以上就是python实现狄克斯特拉算法的详细内容，更多关于python狄克斯特拉的资料请关注好吧啦网其它相关文章！