數(shù)據(jù)結(jié)構(gòu)
1、路由信息
dictRoute = {}
dictRoute[nodeId] = {}
dictRoute[nodeId][nebrId] = distance
操作：
①根據(jù)nodeId找到該node的路由信息
②根據(jù)nebrId找到某一條路由的距離
2、節(jié)點(diǎn)信息
dictNode = {}
dictNode[nodeId] = [shortDis, fatherId, bIsCheck]
操作：
①找到nodes中最短距離的節(jié)點(diǎn)
②查找節(jié)點(diǎn)的shortDis，根據(jù)情況更新shortDis、fatherId
③檢查過(guò)的節(jié)點(diǎn)，更新bIsCheck
功能實(shí)現(xiàn)
/* 找到最短距離節(jié)點(diǎn)的Id，已經(jīng)檢查的不計(jì)算在內(nèi) */
def FindShortNodeId(dictNode):
return shortNodeId
/* dikstra算法流程 */
1、找到最短距離節(jié)點(diǎn)Id，并標(biāo)記已檢查過(guò) （如果節(jié)點(diǎn)Id不存在，表示查找完成）
2、得到最短距離節(jié)點(diǎn)的距離
3、輪詢(xún)最短距離節(jié)點(diǎn)的鄰居節(jié)點(diǎn)
4、計(jì)算鄰居節(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)信息
代碼實(shí)現(xiàn)
import os
import sys
'''
信息輸入：
1、節(jié)點(diǎn)數(shù)目、路由數(shù)目
2、路由信息
3、開(kāi)始節(jié)點(diǎn)、結(jié)束節(jié)點(diǎn)
'''
nodeNum = 0 # 節(jié)點(diǎn)數(shù)目
routeNum = 0 # 路由數(shù)目
listRoute = [] # 臨時(shí)存儲(chǔ)輸入的路由信息
listNodeId = []# 臨時(shí)存儲(chǔ)節(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)
# 輸入開(kāi)始節(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)、是否檢查過(guò)
# 每個(gè)路由字典創(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()
'''
狄克斯特拉實(shí)現(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])
測(cè)試用例及驗(yàn)證
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實(shí)現(xiàn)狄克斯特拉算法的詳細(xì)內(nèi)容，更多關(guān)于python狄克斯特拉的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
您可能感興趣的文章:- Python常用外部指令執(zhí)行代碼實(shí)例
- Python 讀取用戶(hù)指令和格式化打印實(shí)現(xiàn)解析
- 如何安裝并使用conda指令管理python環(huán)境
- python執(zhí)行CMD指令,并獲取返回的方法
- Python機(jī)器學(xué)習(xí)之KNN近鄰算法
- Python機(jī)器學(xué)習(xí)算法之決策樹(shù)算法的實(shí)現(xiàn)與優(yōu)缺點(diǎn)
- 用Python給圖像算法做個(gè)簡(jiǎn)單應(yīng)用界面
- Python實(shí)現(xiàn)七大查找算法的示例代碼
- Python查找算法之插補(bǔ)查找算法的實(shí)現(xiàn)
- python使用ProjectQ生成量子算法指令集
