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狄克斯特拉的資料請關注好吧啦網其它相關文章！