戴克斯特拉演算法（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演算法是目前已知的最快的單源最短路徑演算法，
演算法步驟：
1. 初始時令 S={V0},T={其余頂點}，T中頂點對應的距離值
若存在<V0,Vi>，d(V0,Vi)為<V0,Vi>弧上的權值
若不存在<V0,Vi>，d(V0,Vi)為∞
2. 從T中選取一個其距離值為最小的頂點W且不在S中，加入S
3. 對其余T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值縮短，則修改此距離值
重復上述步驟2、3，直到S中包含所有頂點，即W=Vi為止
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261061.html
標籤：其他
上一篇：SLAM總結（一）