Dijkstra算法

為樂山等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計(jì)制作服務(wù)，及樂山網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)、樂山網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！

迪杰斯特拉算法是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有向圖中最短路徑問題。迪杰斯特拉算法主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。

迪杰斯特拉算法是求從某一個(gè)起點(diǎn)到其余所有結(jié)點(diǎn)的最短路徑，是一對(duì)多的映射關(guān)系，是一種貪婪算法

示例：

算法

算法實(shí)現(xiàn)流程思路：
迪杰斯特拉算法每次只找離起點(diǎn)最近的一個(gè)結(jié)點(diǎn)，并將之并入已經(jīng)訪問過結(jié)點(diǎn)的集合（以防重復(fù)訪問，陷入死循環(huán)），然后將剛找到的最短路徑的結(jié)點(diǎn)作為中間結(jié)點(diǎn)來更新相鄰結(jié)點(diǎn)的路徑長(zhǎng)度，這樣循環(huán)找到圖中一個(gè)個(gè)結(jié)點(diǎn)的最短路徑。

"""
輸入
graph 輸入的圖
src 原點(diǎn)
返回
dis 記錄源點(diǎn)到其他點(diǎn)的最短距離
path 路徑
"""
import json
def dijkstra(graph,src):
  if graph ==None:
    return None
  # 定點(diǎn)集合
  nodes = [i for i in range(len(graph))] # 獲取頂點(diǎn)列表，用鄰接矩陣存儲(chǔ)圖
  # 頂點(diǎn)是否被訪問
  visited = []
  visited.append(src)
  # 初始化dis
  dis = {src:0}# 源點(diǎn)到自身的距離為0
  for i in nodes:
    dis[i] = graph[src][i]
  path={src:{src:[]}} # 記錄源節(jié)點(diǎn)到每個(gè)節(jié)點(diǎn)的路徑
  k=pre=src
  while nodes:
    temp_k = k
    mid_distance=float('inf') # 設(shè)置中間距離無窮大
    for v in visited:
      for d in nodes:
        if graph[src][v] != float('inf') and graph[v][d] != float('inf'):# 有邊
          new_distance = graph[src][v]+graph[v][d]
          if new_distance <= mid_distance:
            mid_distance=new_distance
            graph[src][d]=new_distance # 進(jìn)行距離更新
            k=d
            pre=v
    if k!=src and temp_k==k:
      break
    dis[k]=mid_distance # 最短路徑
    path[src][k]=[i for i in path[src][pre]]
    path[src][k].append(k)

    visited.append(k)
    nodes.remove(k)
    print(nodes)
  return dis,path
if __name__ == '__main__':
  # 輸入的有向圖,有邊存儲(chǔ)的就是邊的權(quán)值，無邊就是float('inf')，頂點(diǎn)到自身就是0
  graph = [ 
    [0, float('inf'), 10, float('inf'), 30, 100],
    [float('inf'), 0, 5, float('inf'), float('inf'), float('inf')],
    [float('inf'), float('inf'), 0, 50, float('inf'), float('inf')],
    [float('inf'), float('inf'), float('inf'), 0, float('inf'), 10],
    [float('inf'), float('inf'), float('inf'), 20, 0, 60],
    [float('inf'), float('inf'), float('inf'), float('inf'), float('inf'), 0]]
  dis,path= dijkstra(graph, 0) # 查找從源點(diǎn)0開始帶其他節(jié)點(diǎn)的最短路徑
  print(dis)
  print(json.dumps(path, indent=4))

當(dāng)前題目：Python實(shí)現(xiàn)Dijkstra算法-創(chuàng)新互聯(lián)
文章分享：http://www.aaarwkj.com/article44/ppcee.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號(hào)、網(wǎng)站營(yíng)銷、Google、品牌網(wǎng)站建設(shè)、App開發(fā)、網(wǎng)站改版

廣告

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