數(shù)據(jù)結(jié)構(gòu)

1、路由信息

dictRoute = {}
dictRoute[nodeId] = {}
dictRoute[nodeId][nebrId] = distance
操作：
①根據(jù)nodeId找到該node的路由信息
②根據(jù)nebrId找到某一條路由的距離

2、節(jié)點信息

dictNode = {}
dictNode[nodeId] = [shortDis, fatherId, bIsCheck]
操作：
①找到nodes中最短距離的節(jié)點
②查找節(jié)點的shortDis，根據(jù)情況更新shortDis、fatherId
③檢查過的節(jié)點，更新bIsCheck

功能實現(xiàn)

/* 找到最短距離節(jié)點的Id，已經(jīng)檢查的不計算在內(nèi) */
def FindShortNodeId(dictNode):
return shortNodeId

/* dikstra算法流程 */
1、找到最短距離節(jié)點Id，并標(biāo)記已檢查過（如果節(jié)點Id不存在，表示查找完成）
2、得到最短距離節(jié)點的距離
3、輪詢最短距離節(jié)點的鄰居節(jié)點
4、計算鄰居節(jié)點的新距離、得到原最短距離，進(jìn)行比較
5、如果新距離原距離，則更新鄰居節(jié)點最短距離
概括為兩步：步驟1 （1）- 找到當(dāng)前最短距離節(jié)點
步驟2（2~5） - 更新最短距離節(jié)點鄰居節(jié)點信息

代碼實現(xiàn)

import os
import sys

'''
信息輸入：
1、節(jié)點數(shù)目、路由數(shù)目
2、路由信息 
3、開始節(jié)點、結(jié)束節(jié)點
'''
nodeNum = 0 # 節(jié)點數(shù)目
routeNum = 0 # 路由數(shù)目
listRoute = [] # 臨時存儲輸入的路由信息
listNodeId = []# 臨時存儲節(jié)點id 

nodeIdStart = ''
nodeIdEnd = ''
dictRoute = {} # 解析后的路由信息
dictNode = {} # 節(jié)點信息
# 輸入節(jié)點數(shù)目、路由數(shù)目
strInput = input()
list0 = strInput.split(' ')
nodeNum = int(list0[0])
routeNum = int(list0[1])

# 輸入路由信息
for index in range(routeNum):
 strInput = input()
 listRoute.append(strInput)
 
# 輸入開始節(jié)點、結(jié)束節(jié)點
strInput = input()
list0 = strInput.split(' ')
nodeIdStart = list0[0]
nodeIdEnd = list0[1]

# 解析得到節(jié)點Id
listNodeId.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) 

# 初始化路由信息字典、節(jié)點信息字典
for nodeId in listNodeId:
 # 節(jié)點字典信息
 dictNode[nodeId] = [10000, '', False] # 最短距離、父節(jié)點、是否檢查過
 # 每個路由字典創(chuàng)建
 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()

'''
狄克斯特拉實現(xiàn)
'''
# 找到最短距離節(jié)點id
def 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)
 
# 打印結(jié)果
listRst = []
nodeId = nodeIdEnd
while 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實現(xiàn)狄克斯特拉算法的詳細(xì)內(nèi)容，更多關(guān)于python狄克斯特拉的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章:

Python常用外部指令執(zhí)行代碼實例
Python 讀取用戶指令和格式化打印實現(xiàn)解析
如何安裝并使用conda指令管理python環(huán)境
python執(zhí)行CMD指令,并獲取返回的方法
Python機器學(xué)習(xí)之KNN近鄰算法
Python機器學(xué)習(xí)算法之決策樹算法的實現(xiàn)與優(yōu)缺點
用Python給圖像算法做個簡單應(yīng)用界面
Python實現(xiàn)七大查找算法的示例代碼
Python查找算法之插補查找算法的實現(xiàn)
python使用ProjectQ生成量子算法指令集

標(biāo)簽：山西山西濟(jì)南海南喀什安康長沙崇左

巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《python實現(xiàn)狄克斯特拉算法》，本文關(guān)鍵詞；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題，煩請?zhí)峁┫嚓P(guān)信息告之我們，我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無關(guān)。