📢📢📢📣📣📣
🌻🌻🌻Hello，大家好我叫是Dream呀，一個有趣的Python部落客，小白一枚，多多關照😜😜😜
🏅🏅🏅CSDN Python領域新星創作者，大二在讀，歡迎大家找我合作學習
💕
💓入門須知：這片樂園從不缺乏天才，努力才是你的最終入場券！🚀🚀🚀
最後，願我們都能在看不到的地方閃閃發光，一起加油進步🍺🍺🍺
🍉🍉🍉“一萬次悲傷，依然會有Dream，我一直在最溫暖的地方等你”，唱的就是我！哈哈哈~🌈🌈🌈
🌟🌟🌟✨✨✨
第七章：狄克斯特拉算法
- 7.1使用狄克斯特拉算法
- 7.2術語
- 7.3負權邊
- 7.4實作
- 📢📢📢最後的福利
廣度優先搜尋用于找出段數最少的路徑，如果你要找出最快的路徑，該咋辦呢？需要用到另一種算法：狄克斯特拉算法。
7.1使用狄克斯特拉算法
四個步驟：
1.找出“最便宜”的節點，即在最短的時間内到達的節點。
2.更新該節點的鄰居的開銷，其含義稍後介紹。
3.重複這個計算過程，直到對圖中的每個節點都這樣做了。
4.計算最終路徑。
第一步：找出最便宜的節點。你站在起點，不知道該前往節點A還是前往節點B。前往這兩個節點需要多少時間呢？
把前往終點時間定義為無限大，你會發現隻看一步的話到B最近；
第二步：計算節點B前往其各個鄰居所需要的時間。突然你又發現了一條經B到A更近的路，這樣對于經B的鄰居A而言，如果找到前往他的更短路徑，就更新其開銷。
第三步：重複！
重複第一步（找出可在最短時間内前往的節點）和第二步（更新節點A的所有鄰居的開銷）
最後一步：計算最終的路徑。
7.2術語
狄克斯特拉算法用于每條邊都有關聯數字的圖，這些數字稱為權重。帶權重的圖稱為權重圖，不帶權重的圖稱為非權重圖。
無向圖意味着兩個節點彼此指向對方，其實就是環！在無向圖中，每條邊都是一個環。 狄克斯特拉算法隻适用于 有向無環圖
7.3負權邊
如果有負權邊，就不能使用狄克斯特拉算法。因為負權邊會導緻這種算法不管用。根據狄克斯特拉算法，沒有比不支付任何費用獲得海報更便宜的方式。（你知道這是不對的！）
有負權邊問題時，書上說可以用另一種算法來實作：貝爾曼——福德算法，但是它沒講，差評！！！
7.4實作
1.首先建立一個散清單：
graph={}
graph["you"]=['alice', 'bob','claiure']
但這裡需要需要同時儲存鄰居和前往鄰居的開銷。例如：起點有兩個鄰居——A和B
2.表示這些邊的權重：
graph['start']={}
graph['start']['a']=6
graph['start']['b']=2
3.下面添加其他節點和鄰居：
graph['a']={}
graph['a']['fin']=1
graph['b']={}
graph['b']['a']=3
graph['b']['fin']=5
graph["fin"]={}#終點沒有任何鄰居
對不知道的開銷，可以将其設定為無窮大：
4.建立開銷表：
infinity=float('inf')
costs={}
costs['a']=6
costs['b']=2
costs['fin']=infinity
5.建立儲存父節點的散清單：
parents={}
parents['a']='start'
parents['b']='start'
parents['fin']=None
6.建立一個數組，存儲記錄處理過的節點：
7.找出開銷最低的節點：
def find_lowest_cost_node(costs):
lowest_cost=float('inf')
lowest_cost_node=None
for node in costs:
cost =costs[node]
if cost<lowest_cost and node not in processed:
lowest_cost=cost
lowest_cost_node=node
return lowest_cost_node
8.最終實作：
node=find_lowest_cost_node(costs)#在未處理的節點中找出開銷最小的點
while node is not None:#這個while循環在所有節點都被處理過後結束
cost=costs[node]
neighbors=graph[node]
for n in neighbors.keys():#周遊目前節點的所有鄰居
new_cost=cost+neighbors[n]
if costs[n]>new_cost:#如果經目前節點前往該鄰居更近
costs[n]=new_cost#就更新其鄰居開銷
parents[n]=node#同時将該鄰居的父點設定為目前節點
processed.append(node)#将目前的節點标記為處理過
node=find_lowest_cost_node(costs)#找出接下來要處理的節點，并循環
📢📢📢最後的福利
🍋🍋🍋最後一點小福利帶給大家：如果想快速上手python的小夥伴們，這個詳細整理PPT可以迅速幫助大家打牢python基礎，需要的小夥伴們可以下載下傳一下 Python入門基礎教程全套+小白速成+學不會來找我！ 🍻🍻🍻
還有自制表白神器，需要自取：
Python表白神器，源碼+解析+各種完美配置+浪漫新穎 🍻🍻🍻
🌲🌲🌲 好啦，這就是今天要分享給大家的全部内容了
❤️❤️❤️如果你喜歡的話，就不要吝惜你的一鍵三連了~
