數(shù)據(jù)結(jié)構(gòu)(六) 迪杰斯特拉算法的最短路徑（Swift面向?qū)ο蟀妫?/a>

上篇博客我們?cè)敿?xì)的介紹了兩種經(jīng)典的最小生成樹的算法，本篇博客我們就來詳細(xì)的講一下最短路徑的經(jīng)典算法----迪杰斯特拉算法。首先我們先聊一下什么是最短路徑，這個(gè)還是比較好理解的。比如我要從北京到濟(jì)南，而從北京到濟(jì)南有好多條道路，那么最短的那一條就是北京到濟(jì)南的最短路徑，也是我們今天要求的最短路徑。

因?yàn)樽疃搪窂绞腔谟邢驁D來計(jì)算的，所以我們還是使用上幾篇關(guān)于圖的博客中使用的示例。不過我們今天博客中用到的圖是有向圖，所以我們要講上篇博客的無向圖進(jìn)行改造，改成有向圖，然后在有向圖的基礎(chǔ)上給出最小生成樹的解決方案。本篇博客我們的思路與之前數(shù)據(jù)結(jié)構(gòu)相關(guān)博客的風(fēng)格保持一致，首先我們先給出迪杰斯特拉算法的原理以及詳細(xì)的示意圖，然后根據(jù)這些示意圖給出具體的實(shí)現(xiàn)方案。

 

一、迪杰斯特拉算法原理解析

在博客的第一部分，我們不談任何與代碼相關(guān)的內(nèi)容，只談迪杰斯特拉算法的原理以及生成最短路徑的具體步驟。下方我們會(huì)給出迪杰斯特拉算法的計(jì)算最短路徑的每一步，并給出每一步具體的說明。廢話少說，進(jìn)入本部分的主題。

 

1、有向帶權(quán)圖

本篇博客依然采取我們之前用的圖的結(jié)構(gòu)。不過我們本篇博客使用的是有向圖。下方這張圖就是是我們之前使用的無向圖轉(zhuǎn)換過來的，只是給之前的圖的邊添加的具體的方向，其他的并為改動(dòng)。由無向圖轉(zhuǎn)換后的有向圖如下所示，我們將在下方的圖的基礎(chǔ)上計(jì)算出從A到D的最短路徑。

2.迪杰斯特拉算法的具體步驟

下圖就是求上圖中A->D的最短路徑時(shí)使用迪杰斯特拉算法的具體步驟。迪杰斯特拉算法主要核心思想是由起始結(jié)點(diǎn)開始，慢慢的由尾結(jié)點(diǎn)擴(kuò)散。直到擴(kuò)展到尾結(jié)點(diǎn)位置。下方我們將根據(jù)每個(gè)步驟給出具體的介紹：