dictRoute = {}
dictRoute[nodeId] = {}
dictRoute[nodeId][nebrId] = distance
操作：
①根據(jù)nodeId找到該node的路由信息
②根據(jù)nebrId找到某一條路由的距離
dictNode = {}
dictNode[nodeId] = [shortDis, fatherId, bIsCheck]
操作：
①找到nodes中最短距離的節(jié)點(diǎn)
②查找節(jié)點(diǎn)的shortDis，根據(jù)情況更新shortDis、fatherId
③檢查過的節(jié)點(diǎn)，更新bIsCheck
/* 找到最短距離節(jié)點(diǎn)的Id，已經(jīng)檢查的不計算在內(nèi) */
def FindShortNodeId(dictNode):
return shortNodeId
/* dikstra算法流程 */
1、找到最短距離節(jié)點(diǎn)Id，并標(biāo)記已檢查過 （如果節(jié)點(diǎn)Id不存在，表示查找完成）
2、得到最短距離節(jié)點(diǎn)的距離
3、輪詢最短距離節(jié)點(diǎn)的鄰居節(jié)點(diǎn)
4、計算鄰居節(jié)點(diǎn)的新距離、得到原最短距離，進(jìn)行比較
5、如果新距離 原距離，則更新鄰居節(jié)點(diǎn)最短距離
概括為兩步：步驟1 （1）- 找到當(dāng)前最短距離節(jié)點(diǎn)
步驟2（2~5） - 更新最短距離節(jié)點(diǎn)鄰居節(jié)點(diǎn)信息
import os
import sys
'''
信息輸入：
1、節(jié)點(diǎn)數(shù)目、路由數(shù)目
2、路由信息
3、開始節(jié)點(diǎn)、結(jié)束節(jié)點(diǎn)
'''
nodeNum = 0 # 節(jié)點(diǎn)數(shù)目
routeNum = 0 # 路由數(shù)目
listRoute = [] # 臨時存儲輸入的路由信息
listNodeId = []# 臨時存儲節(jié)點(diǎn)id
nodeIdStart = ''
nodeIdEnd = ''
dictRoute = {} # 解析后的路由信息
dictNode = {} # 節(jié)點(diǎn)信息
# 輸入節(jié)點(diǎn)數(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é)點(diǎn)、結(jié)束節(jié)點(diǎn)
strInput = input()
list0 = strInput.split(' ')
nodeIdStart = list0[0]
nodeIdEnd = list0[1]
# 解析得到節(jié)點(diǎn)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é)點(diǎn)信息字典
for nodeId in listNodeId:
# 節(jié)點(diǎn)字典信息
dictNode[nodeId] = [10000, '', False] # 最短距離、父節(jié)點(diǎn)、是否檢查過
# 每個路由字典創(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é)點(diǎn)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（找不到終點(diǎn)）
輸入：
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)文章！
標(biāo)簽：安慶 西安 錦州 股票 天水 日照 白城 隨州
巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《python實現(xiàn)狄克斯特拉算法》，本文關(guān)鍵詞 python,實現(xiàn),狄克,斯特拉,；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題，煩請?zhí)峁┫嚓P(guān)信息告之我們，我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無關(guān)。
