一、 迪杰斯特拉算法思想
Dijkstra算法主要針對的是有向圖的單元最短路徑問題,且不能出現(xiàn)權(quán)值為負(fù)的情況!Dijkstra算法類似于貪心算法,其應(yīng)用根本在于最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)。
最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì):
如果P(i,j)={Vi…Vk…Vs…Vj}是從頂點(diǎn)i到j(luò)的最短路徑,k和s是這條路徑上的一個(gè)中間頂點(diǎn),那么P(k,s)必定是從k到s的最短路徑。
證明:
假設(shè)P(i,j)={Vi…Vk…Vs…Vj}是從頂點(diǎn)i到j(luò)的最短路徑,則有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是從k到s的最短距離,那么必定存在另一條從k到s的最短路徑P(k,s),那么P(i,j)=P(i,k)+P(k,s)+P(s,j)<P(i,j)。則與P(i,j)是從i到j(luò)的最短路徑相矛盾。因此該性質(zhì)得證。
因此,Dijkstra算法描述如下:
Dijikstra算法描述如下:
假設(shè)存在G=<V,E>,源頂點(diǎn)為V0,S={V0},distance[i]記錄V0到i的最短距離,matrix[i][j]記錄從i到j(luò)的邊的權(quán)值,即兩點(diǎn)之間的距離。
1)從V-S中選擇使dist[i]值最小的頂點(diǎn)i,將i加入到U中;
2)更新與i直接相鄰頂點(diǎn)的dist值。dist[j]=min{dist[j],dist[i]+matrix[i][j]}
3)直到S=V,所有頂點(diǎn)都包含進(jìn)來了,算法停止。
二、 具體操作步驟
根據(jù)其算法思想,確立操作步驟如下:
(1) 初始時(shí),S只包含起點(diǎn)s;U包含除s外的其他頂點(diǎn),且U中頂點(diǎn)的距離為"起點(diǎn)s到該頂點(diǎn)的距離"[例如,U中頂點(diǎn)v的距離為(s,v)的長度,然后s和v不相鄰,則v的距離為∞]。
(2) 從U中選出"距離最短的頂點(diǎn)k",并將頂點(diǎn)k加入到S中;同時(shí),從U中移除頂點(diǎn)k。
(3) 更新U中各個(gè)頂點(diǎn)到起點(diǎn)s的距離。之所以更新U中頂點(diǎn)的距離,是由于上一步中確定了k是求出最短路徑的頂點(diǎn),從而可以利用k來更新其它頂點(diǎn)的距離;例如,(s,v)的距離可能大于(s,k)+(k,v)的距離。
(4) 重復(fù)步驟(2)和(3),直到遍歷完所有頂點(diǎn)。
三、代碼
def dijkstra(s, used, cost, distance, n): distance[s] = 0 while True: # v在這里相當(dāng)于是一個(gè)哨兵,對包含起點(diǎn)s做統(tǒng)一處理! v = -1 # 從未使用過的頂點(diǎn)中選擇一個(gè)距離最小的頂點(diǎn) for u in range(n): if not used[u] and (v == -1 or distance[u] < distance[v]): v = u if v == -1: # 說明所有頂點(diǎn)都維護(hù)到S中了! break # 將選定的頂點(diǎn)加入到S中, 同時(shí)進(jìn)行距離更新 used[v] = True # 更新U中各個(gè)頂點(diǎn)到起點(diǎn)s的距離。之所以更新U中頂點(diǎn)的距離,是由于上一步中確定了k是求出最短路徑的頂點(diǎn),從而可以利用k來更新其它頂點(diǎn)的距離;例如,(s,v)的距離可能大于(s,k)+(k,v)的距離。 for u in range(n): distance[u] = min(distance[u], distance[v] + cost[v][u]) return distance n, m, T = map(int, input().split()) # 標(biāo)記數(shù)組:used[v]值為False說明改頂點(diǎn)還沒有訪問過,在S中,否則在U中! used = [False for _ in range(n)] # 距離數(shù)組:distance[i]表示從源點(diǎn)s到i的最短距離,distance[s]=0 distance = [float('inf') for _ in range(n)] # cost[u][v]表示邊e=(u,v)的權(quán)值,不存在時(shí)設(shè)為INF cost = [[float('inf') for _ in range(n)] for _ in range(n)] for _ in range(m): e = list(map(int, input().split())) cost[e[0] - 1][e[1] - 1] = e[2] dis1 = dijkstra(0, used[:], cost, distance[:], n) d1 = dis1[-1] dis2 = dijkstra(n-1, used[:], cost, distance[:], n) d2 = dis2[0] print((d1+d2)*T)
文章題目:Python實(shí)現(xiàn)迪杰斯特拉算法過程解析-創(chuàng)新互聯(lián)
文章位置:http://www.rwnh.cn/article30/ijjso.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供品牌網(wǎng)站設(shè)計(jì)、企業(yè)網(wǎng)站制作、企業(yè)建站、小程序開發(fā)、網(wǎng)站收錄、網(wǎng)站維護(hù)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容