‘‘‘
inf：表示正無窮，初始化不與定點相連的節點的距離
visited[ver_num]：表示是否已經經歷過該節點
ver_num：當前節點下標
cost[u][v]:表示u和v之間路徑的長度
list表示鄰接矩陣
path表示當前節點的前驅節點
distance表示當前最短路徑
‘‘‘
#?測試用例
‘‘‘
????????武大????地大????圖書城??光谷????華科
武大??????0??????6???????24?????11??????inf
地大?????inf?????0???????inf????4???????8
圖書城???inf?????inf?????0??????11??????inf?
光谷?????inf?????5???????9??????0???????7
華科?????inf?????inf?????inf????5???????inf
‘‘‘

list?=?[
????[062411float（“inf“）]
????[float（“inf“）0float（“inf“）48]
????[float（“inf“）float（“inf“）011float（“inf“）]
????[float（“inf“）5907]
????[float（“inf“）float（“inf“）float（“inf“）5float（“inf“）]
]

dicts?=?{
????‘0‘:‘武大‘
????‘1‘:‘地大‘
????‘2‘:‘圖書城‘
????‘3‘:‘光谷‘
????‘4‘:‘華科‘
}

#?測試5個節點
ver_num?=?5

#?將每一個節點都標記為False
visited?=?[False?for?_?in?range（ver_num）]

#?將所有的節點間距離聲明為inf
cost?=?[[float（‘inf‘）?for?_?in?range（ver_num）]?for?_?in?range（ver_num）]

#?定義一個存放路徑的下標列表，即當前節點的前驅節點
path?=?[]

#?定義列表存放最短路徑長度
distance?=?[]

def?main（）:

????#?將節點間權重值初始化
????init_matrix（costlist）
????#?打印當前鄰接矩陣
????print_matrix（cost）
????#?初始化最短路徑distance
????init_distance（distancecost）
????#?初始化路徑列表path
????init_path（pathcost）
????#?進行算法主體部分從0點開始
????dijkstra（0costpathdistancevisited）
????#?選擇路徑?從武漢到其他四個地方
????choose_place（dicts）

#?打印當前存有權值的矩陣
def?print_matrix（cost）:
????#?print（cost）???用于測試
????for?_?in?cost:
????????for?row?in?range（len（_））:
????????????print（_[row]end?=?“\t“）
????????print（“\n“）


#?初始化鄰接矩陣
def?init_matrix（costlist）:
????for?_?in?range（ver_num）:
????????cost[_]?=?list[_][:]


def?init_distance（distancecost）:
????#?暫時用0作為源點
????#?print（cost[0]）
????for?i?in?range（5）:
????????distance.append（cost[0][i]）
????????print（distance[i]）

def?init_path（pathcost）:
????#?針對源點，將是否與源點之間有邊進行初始化
????#?有邊則進行記錄其前驅節點為0，無邊則記錄其其前驅為-1
????path.append（-1）
????for?i?in?range（1len（cost[0]））:
????????if?cost[0][i]?==?float（“inf“）:
????????????path.append（-1）
????????else:
????????????path.append（0）
????print（path）


#?進行迪杰斯特拉算法?以0節點為標準
def?dijkstra（scostpathdistancevisited）:
????#?標記已經訪問
????visited[s]?=?True
????
????while?True:
????????ver?=?-1
????????#?尋找當前未被標記的最小邊對應的節點
????????ver_min?=?float（“inf“）
????????for?u?in?range（ver_num）:
????????????if?visited[u]?==?False?and?distance[u]?????????????????ver_min?=?distance[u]
????????????????ver?=?u
????????#?測試每次選擇的節點
????????#?print（ver）

????????#?while循環結束條件
????????if?False?not?in?visited:
????????????break

????????visited[ver]?=?True

????????#?更新當前最短路徑
????????for?v?in?range（ver_num）:
????????????#?distance[v]?=?min（distance[v]distance[ver]?+?cost[ver][v]）
????????????
????????????if?distance[v]?>?distance[ver]?+?cost[ver][v]:
????????????????distance[v]?=?distance[ver]?+?cost[ver][v]
????????????????#?更新path
????????????????path[v]?=?ver
????????????#?print（distance[v]）
????????????#?暫時沒有更新path
????#?print（distance）
????#?print（path）

#?選擇目的

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????4512??2020-09-27?20:37??算法\major_dijkstra.py
?????目錄???????????0??2020-09-27?20:58??算法\