python實(shí)現(xiàn)Dijkstra靜態(tài)尋路算法-創(chuàng)新互聯(lián)

算法介紹

成都創(chuàng)新互聯(lián)公司自成立以來(lái)，一直致力于為企業(yè)提供從網(wǎng)站策劃、網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、網(wǎng)站制作、電子商務(wù)、網(wǎng)站推廣、網(wǎng)站優(yōu)化到為企業(yè)提供個(gè)性化軟件開(kāi)發(fā)等基于互聯(lián)網(wǎng)的全面整合營(yíng)銷(xiāo)服務(wù)。公司擁有豐富的網(wǎng)站建設(shè)和互聯(lián)網(wǎng)應(yīng)用系統(tǒng)開(kāi)發(fā)管理經(jīng)驗(yàn)、成熟的應(yīng)用系統(tǒng)解決方案、優(yōu)秀的網(wǎng)站開(kāi)發(fā)工程師團(tuán)隊(duì)及專(zhuān)業(yè)的網(wǎng)站設(shè)計(jì)師團(tuán)隊(duì)。

迪科斯徹算法使用了廣度優(yōu)先搜索解決賦權(quán)有向圖或者無(wú)向圖的單源最短路徑問(wèn)題，算法最終得到一個(gè)最短路徑樹(shù)。該算法常用于路由算法或者作為其他圖算法的一個(gè)子模塊。

當(dāng)然目前也有人將它用來(lái)處理物流方面，以獲取代價(jià)最小的運(yùn)送方案。

算法思路

Dijkstra算法采用的是一種貪心的策略。

1.首先，聲明一個(gè)數(shù)組dis來(lái)保存源點(diǎn)到各個(gè)頂點(diǎn)的最短距離和一個(gè)保存已經(jīng)找到了最短路徑的頂點(diǎn)的集合T。
2.其次，原點(diǎn) s 的路徑權(quán)重被賦為 0 （dis[s] = 0）。若對(duì)于頂點(diǎn) s 存在能直接到達(dá)的邊（s,m），則把dis[m]設(shè)為w（s, m）,同時(shí)把所有其他（s不能直接到達(dá)的）頂點(diǎn)的路徑長(zhǎng)度設(shè)為無(wú)窮大。初始時(shí)，集合T只有頂點(diǎn)s。
3.從dis數(shù)組選擇最小值，則該值就是源點(diǎn)s到該值對(duì)應(yīng)的頂點(diǎn)的最短路徑，并且把該點(diǎn)加入到T中，此時(shí)完成一個(gè)頂點(diǎn)。
4.再次，看看新加入的頂點(diǎn)是否可以到達(dá)其他頂點(diǎn)并且看看通過(guò)該頂點(diǎn)到達(dá)其他點(diǎn)的路徑長(zhǎng)度是否比源點(diǎn)直接到達(dá)短，如果是，那么就替換這些頂點(diǎn)在dis中的值。
5.最后，從dis中找出最小值，重復(fù)上述動(dòng)作，直到T中包含了圖的所有頂點(diǎn)（可以到達(dá)的）。

算法圖形演示

現(xiàn)在有圖如下：

每個(gè)線(xiàn)的權(quán)重以及標(biāo)識(shí)如圖所示。

第一步：

建立dis數(shù)組和T數(shù)組。
首先從起點(diǎn)A 開(kāi)始，將A可以直接到達(dá)的頂點(diǎn)的權(quán)重記錄在dis數(shù)組中，無(wú)法直達(dá)的記錄無(wú)窮大（當(dāng)前使用FFFF表示無(wú)窮大）。

將當(dāng)前選擇的頂點(diǎn)加入數(shù)組T:

第二步：

從dis數(shù)組中選擇一個(gè)不在T數(shù)組中的頂點(diǎn)的最小權(quán)重值的頂點(diǎn)，當(dāng)前選擇為B頂點(diǎn)，并將B可以直接到達(dá)的頂點(diǎn)的相關(guān)權(quán)重和當(dāng)前dis中的權(quán)重值比較，如果當(dāng)前dis權(quán)重值大，則替換：

將B加入數(shù)組T:

第三步：

依次選擇頂點(diǎn)C：

將C加入數(shù)組T:

第四步：

依次選擇頂點(diǎn)D：

將D加入數(shù)組T:

第五步：

依次選擇頂點(diǎn)E：

將E加入數(shù)組T:

第六步：

依次選擇頂點(diǎn)F：

將F加入數(shù)組T:

因?yàn)樗械捻旤c(diǎn)都已經(jīng)在T數(shù)組中了，算法結(jié)束。
這樣就求得了從A點(diǎn)到各個(gè)頂點(diǎn)的最優(yōu)解。

可以看到A頂點(diǎn)無(wú)法直達(dá)F頂點(diǎn)。

代碼表示：

(代碼中使用999代表FFF)

#encoding:utf-8

import copy
"""
圖的表示方式
鄰接矩陣
999代表無(wú)限遠(yuǎn)
"""
tuG=[[0, 10, 20, 999, 999, 999],
 [999, 0, 999, 20, 70, 999],
 [999, 999, 0, 50, 30, 999],
 [999, 999, 999, 0, 999, 999],
 [999, 999, 999, 10, 0, 999],
 [999, 999, 999, 20, 20, 0]];

tuX = 6;

# 設(shè)置原點(diǎn)到其他定點(diǎn)的各個(gè)距離
dis = copy.deepcopy(tuG[0]);

def Dijkstra(G,v0):
 """
 使用 Dijkstra 算法計(jì)算指定點(diǎn) v0 到圖 G 中任意點(diǎn)的最短路徑的距離
 INF 為設(shè)定的無(wú)限遠(yuǎn)距離值
 """
 t = [];
 minv = v0;

 while len(t) <= tuX:
 t.append(minv);
 #以當(dāng)前點(diǎn)的中心向外擴(kuò)散
 for w in range(0, tuX):
  if dis[minv] + G[minv][w] < dis[w]:
  dis[w] = dis[minv] + G[minv][w]

 tmp = 1000;
 for i in range(0, tuX):
  tmpFlag = False;
  for j in range(0, len(t)):
  if i == t[j]:
   tmpFlag = True;
   break;

  if tmpFlag == True:
  continue;

  if tmp > dis[i]:
  tmp = dis[i];
  minv = i;

if __name__ == '__main__': 
 Dijkstra(tuG,0); 
 print dis;

分享題目：python實(shí)現(xiàn)Dijkstra靜態(tài)尋路算法-創(chuàng)新互聯(lián)
URL鏈接：http://muchs.cn/article12/djicdc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供小程序開(kāi)發(fā)、Google、微信公眾號(hào)、服務(wù)器托管、外貿(mào)建站、關(guān)鍵詞優(yōu)化

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容