迪杰斯特拉（Dijkstra）算法主要是針對沒有負(fù)值的有向圖，求解其中的單一起點(diǎn)到其他頂點(diǎn)的最短路徑算法。

成都創(chuàng)新互聯(lián)公司是專業(yè)的濉溪網(wǎng)站建設(shè)公司，濉溪接單;提供網(wǎng)站制作、成都網(wǎng)站建設(shè),網(wǎng)頁設(shè)計,網(wǎng)站設(shè)計,建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行濉溪網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊,希望更多企業(yè)前來合作!

1 算法原理

迪杰斯特拉（Dijkstra）算法是一個按照路徑長度遞增的次序產(chǎn)生的最短路徑算法。下圖為帶權(quán)值的有向圖，作為程序中的實(shí)驗(yàn)數(shù)據(jù)。

其中，帶權(quán)值的有向圖采用鄰接矩陣graph來進(jìn)行存儲，在計算中就是采用n*n的二維數(shù)組來進(jìn)行存儲，v0-v5表示數(shù)組的索引編號0-5，二維數(shù)組的值表示節(jié)點(diǎn)之間的權(quán)值，若兩個節(jié)點(diǎn)不能通行，比如，v0->v1不能通行，那么graph[0,1]=+∞ （采用計算機(jī)中大正整數(shù)來進(jìn)行表示）。那如何求解從v0每個v節(jié)點(diǎn)的最短路徑長度呢?

首先，引進(jìn)一個輔助數(shù)組cost，它的每個值cost[i]表示當(dāng)前所找到的從起始點(diǎn)v0到終點(diǎn)vi的最短路徑的權(quán)值（長度花費(fèi)），該數(shù)組的初態(tài)為：若從v0到vi有弧，則cost[i]為弧上的權(quán)值，否則置cost[i]為+∞。

顯然，長度為：cost[j]=Min_i(graph[0,i] | v_i in V)的路徑就是從v0出發(fā)的長度最短的一條最短路徑。此路徑為(v_0,v_j) ，那么下次長度次短的路徑必定是弧(v_0,v_i)上的權(quán)值cost[i](v_i in V)，或者是cost[k](v_k in S)和弧(v_k,v_i)的權(quán)值之和。其中V：待求解最短路徑的節(jié)點(diǎn)j集合；S：已求解最短路徑的節(jié)點(diǎn)集合。

2 算法流程

根據(jù)上面的算法原理分析，下面描述算法的實(shí)現(xiàn)流程。

初始化：初始化輔助數(shù)組cost，從v0出發(fā)到圖上其余節(jié)點(diǎn)v的初始權(quán)值為：cost[i]=graph[0,i] | v_i in V ；初始化待求節(jié)點(diǎn)S集合，它的初始狀態(tài)為始點(diǎn)，V集合，全部節(jié)點(diǎn)-始節(jié)點(diǎn)。

選擇節(jié)點(diǎn)v_j ，使得cost[j]=Min ( cost[i] | v_i in V -S ) ，v_j 就是當(dāng)前求的一條從v0出發(fā)的最短路徑的終點(diǎn)，修改S集合，使得 S=S + V_j ，修改集合V = V - V_j。

修改從v0出發(fā)到節(jié)點(diǎn)V-S上任一頂點(diǎn) v_k 可達(dá)的最短路徑，若cost[j]+graph[j,k]<cost[k] ，則修改cost[k]為：cost[k]=cost[j]+graph[j,k] 。

重復(fù)操作2，3步驟，直到求解集合V中的所有節(jié)點(diǎn)為止。

其中最短路徑的存儲采用一個path整數(shù)數(shù)組，path[i]的值記錄vi的前一個節(jié)點(diǎn)的索引，通過path一直追溯到起點(diǎn)，就可以找到從vi到起始節(jié)點(diǎn)的最短路徑。比如起始節(jié)點(diǎn)索引為0，若path[3]=4, path[4]=0；那么節(jié)點(diǎn)v2的最短路徑為，v0->v4->v3。

3 算法實(shí)現(xiàn)

采用python語言對第2節(jié)中的算法流程進(jìn)行實(shí)現(xiàn)，關(guān)鍵代碼如下。

3.1 最短路徑代碼

#!/bin/python
# -*- coding:utf-8 -*-

def dijkstra(graph, startIndex, path, cost, max):
  """
  求解各節(jié)點(diǎn)最短路徑，獲取path，和cost數(shù)組，
  path[i] 表示vi節(jié)點(diǎn)的前繼節(jié)點(diǎn)索引，一直追溯到起點(diǎn)。
  cost[i] 表示vi節(jié)點(diǎn)的花費(fèi)
  """
  lenth = len(graph)
  v = [0] * lenth
  # 初始化 path，cost，V
  for i in range(lenth):
    if i == startIndex:
      v[startIndex] = 1
    else:
      cost[i] = graph[startIndex][i]
      path[i] = (startIndex if (cost[i] < max) else -1)
  # print v, cost, path
  for i in range(1, lenth):
    minCost = max
    curNode = -1
    for w in range(lenth):
      if v[w] == 0 and cost[w] < minCost:
        minCost = cost[w]
        curNode = w
    # for 獲取最小權(quán)值的節(jié)點(diǎn)
    if curNode == -1: break
    # 剩下都是不可通行的節(jié)點(diǎn)，跳出循環(huán)
    v[curNode] = 1
    for w in range(lenth):
      if v[w] == 0 and (graph[curNode][w] + cost[curNode] < cost[w]):
        cost[w] = graph[curNode][w] + cost[curNode] # 更新權(quán)值
        path[w] = curNode # 更新路徑
    # for 更新其他節(jié)點(diǎn)的權(quán)值（距離）和路徑
  return path

if __name__ == '__main__':
  max = 2147483647
  graph = [
    [max, max, 10, max, 30, 100],
    [max, max, 5, max, max, max],
    [max, max, max, 50, max, max],
    [max, max, max, max, max, 10],
    [max, max, max, 20, max, 60],
    [max, max, max, max, max, max],
    ]
  path = [0] * 6
  cost = [0] * 6
  print dijkstra(graph, 0, path, cost, max)

當(dāng)前文章：python實(shí)現(xiàn)Dijkstra算法的最短路徑問題-創(chuàng)新互聯(lián)
網(wǎng)站網(wǎng)址：http://chinadenli.net/article16/cdhggg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供小程序開發(fā)、用戶體驗(yàn)、網(wǎng)站導(dǎo)航、面包屑導(dǎo)航、App設(shè)計、企業(yè)建站

廣告

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