資源簡介
戴克斯特拉算法（Dijkstra’s algorithm）是由荷蘭計算機科學家艾茲赫爾·戴克斯特拉提出。迪科斯徹算法使用了廣度優先搜索解決非負權有向圖的單源最短路徑問題，算法最終得到一個最短路徑樹。該算法常用于路由算法或者作為其他圖算法的一個子模塊。
該算法的輸入包含了一個有權重的有向圖 G，以及G中的一個來源頂點 S。我們以 V 表示 G 中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u, v) 表示從頂點 u 到 v 有路徑相連。我們以 E 表示G中所有邊的集合，而邊的權重則由權重函數 w: E → [0, ∞] 定義。因此，w(u, v) 就是從頂點 u 到頂點 v 的非負權重（weight）。邊的權重可以想像成兩個頂點之間的距離。任兩點間路徑的權重，就是該路徑上所有邊的權重總和。已知有 V 中有頂點 s 及 t，Dijkstra 算法可以找到 s 到 t的最低權重路徑(例如，最短路徑)。這個算法也可以在一個圖中，找到從一個頂點 s 到任何其他頂點的最短路徑。對于不含負權的有向圖，Dijkstra算法是目前已知的最快的單源最短路徑算法。
代碼片段和文件信息
import?time
import?heapq
def?dijkstra（Gstart）:?????###dijkstra算法????
????INF?=?999999999
????dis?=?dict（（keyINF）?for?key?in?G）????#?start到每個點的距離
????dis[start]?=?0
????vis?=?dict（（keyFalse）?for?key?in?G）????#是否訪問過，1位訪問過，0為未訪問
????###堆優化
????pq?=?[]????#存放排序后的值
????heapq.heappush（pq[dis[start]start]）
????t3?=?time.time（）
????path?=?dict（（key[start]）?for?key?in?G）????#記錄到每個點的路徑
????while?len（pq）>0:
????????v_disv?=?heapq.heappop（pq）????#未訪問點中距離最小的點和對應的距離
????????if?vis[v]?==?True:
????????????continue
????????vis[v]?=?True
????????p?=?path[v].copy（）????#到v的最短路徑
????????for?node?in?G[v]:????#與v直接相連的點
????????????new_dis?=?dis[v]?+?float（G[v][node]）
????????????if?- 上一篇：python TCP聊天程序
- 下一篇：GRU神經網絡 Python代碼
評論
共有 條評論
川公網安備 51152502000135號