用什麼演算法可以模擬路徑

Ⅰ A*演算法——啟發式路徑搜索

A*是一種路徑搜索演算法，比如為游戲中的角色規劃行動路徑。

A* 演算法的輸入是， 起點（初始狀態） 和 終點（目標狀態） ，以及兩點間 所有可能的路徑 ，以及涉及到的 中間節點（中間狀態） ，每兩個節點間的路徑的 代價 。

一般還需要某種 啟發函數 ，即從任意節點到終點的近似代價，啟發函數能夠非常快速的估算出該代價值。

輸出是從 起點到終點的最優路徑 ，即代價最小。同時，好的啟發函數將使得這一搜索運算盡可能高效，即搜索盡量少的節點/可能的路徑。

f(n)=g(n)+h(n)

f(n) 是從初始狀態經由狀態n到目標狀態的代價估計

g(n) 是在狀態空間中從初始狀態到狀態n的實際代價

h(n) 是從狀態n到目標狀態的最佳路徑的估計代價

A*演算法是從起點開始，檢查所有可能的擴展點（它的相鄰點），對每個點計算g+h得到f，在所有可能的擴展點中，選擇f最小的那個點進行擴展，即計算該點的所有可能擴展點的f值，並將這些新的擴展點添加到擴展點列表（open list）。當然，忽略已經在列表中的點、已經考察過的點。

不斷從open list中選擇f值最小的點進行擴展，直到到達目標點（成功找到最優路徑），或者節點用完，路徑搜索失敗。

演算法步驟：

參考

A* 演算法步驟的詳細說明請參考 A*尋路演算法 ，它包含圖文案例清楚的解釋了A*演算法計算步驟的一些細節，本文不再詳細展開。

看一下上面參考文檔中的案例圖，最終搜索完成時，藍色邊框是close list中的節點，綠色邊框是open list中的節點，每個方格中三個數字，左上是f（=g+h），左下是g（已經過路徑的代價），右下是h（估計未經過路徑的代價）。藍色方格始終沿著f值最小的方向搜索前進，避免了對一些不好的路徑（f值較大）的搜索。（圖片來自 A*尋路演算法 ）

現在我們可以理解，A*演算法中啟發函數是最重要的，它有幾種情況：

1) h(n) = 0
一種極端情況，如果h(n)是0，則只有g(n)起作用，此時A*演變成Dijkstra演算法，這保證能找到最短路徑。但效率不高，因為得不到啟發。

2) h(n) < 真實代價
如果h(n)經常都比從n移動到目標的實際代價小（或者相等），則A*保證能找到一條最短路徑。h(n)越小，A*擴展的結點越多，運行就得越慢。越接近Dijkstra演算法。

3) h(n) = 真實代價
如果h(n)精確地等於從n移動到目標的代價，則A*將會僅僅尋找最佳路徑而不擴展別的任何結點，這會運行得非常快。盡管這不可能在所有情況下發生，你仍可以在一些特殊情況下讓它們精確地相等（譯者：指讓h(n)精確地等於實際值）。只要提供完美的信息，A*會運行得很完美，認識這一點很好。

4) h(n) > 真實代價
如果h(n)有時比從n移動到目標的實際代價高，則A*不能保證找到一條最短路徑，但它運行得更快。

5) h(n) >> 真實代價
另一種極端情況，如果h(n)比g(n)大很多，則只有h(n)起作用，A*演變成BFS演算法。

關於啟發函數h、Dijkstra演算法、BFS（最佳優先搜索）演算法、路徑規劃情況下啟發函數的選擇、演算法實現時List的數據結構、演算法變種等等更多問題，請參考： A*演算法

Ⅱ 路徑分析的最優路徑分析方法

1．道路預處理
進行道路數據錄入時，往往在道路的交叉接合處出現重疊或相離的情況，不宜計算機處理。因此，需要對原始數據進行預處理，使道路接合符合處理要求。進行預處理時，取每條線段的首末節點坐標為圓心，以給定的閾值為半徑作圓域，判斷其他線段是否與圓域相交，如果相交，則相交的各個線對象共用一個節點號。
2．道路自動斷鏈
對道路進行預處理之後即可獲得比較理想的數據，在此基礎上再進行道路的自動斷鏈。步驟如下：
（1）取出所有線段記錄數n，從第一條線段開始；
（2）找出所有與之相交的線段並求出交點數m；
（3）將m個交點和該線段節點在判斷無重合後進行排序；
（4）根據交點數量，該線段被分成m+1段；
（5）第一段在原始位置不變，後m段從記錄尾開始遞增；
（6）重復（2）～（5），循環至n。
3．節點匹配
拓撲關系需使用統一的節點。節點匹配方法是按記錄順序將所有線段的始末點加上相應節點號，坐標相同的節點共用一個節點號，與前面所有線段首末點都不相同的節點按自然順序遞增1。
4．迪傑克斯特拉（Dijkstra）演算法
經典的圖論與計算機演算法的有效結合，使得新的最短路徑演算法不斷涌現。目前提出的最短路徑演算法中，使用最多、計算速度比較快，又比較適合於計算兩點之間的最短路徑問題的數學模型就是經典的Dijkstra演算法。
該演算法是典型的單源最短路徑演算法，由Dijkstra EW於1959年提出，適用於所有弧的權均為非負的情況，主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。該演算法的基本思想是：認為兩節點間最佳路徑要麼是直接相連，要麼是通過其他已找到的與起始點的最佳路徑的節點中轉點。定出起始點P0後，定能找出一個與之直接相連且路徑長度最短的節點，設為P1，P0到P1就是它們間的最佳路徑。
Dijkstra演算法的基本流程如下：首先將網路中所有節點分成兩組，一組包含了已經確定屬於最短路徑中點的集合，記為S（該集合在初始狀態只有一個源節點，以後每求得一條最短路徑，就將其加入到集合S中，直到全部頂點都加入到S中，演算法就結束了）；另一組是尚未確定最短路徑的節點的集合，記為V，按照最短路徑長度遞增的次序依次把第二組的頂點加入到第一組中，在加入的過程中總保持從源點到S中各頂點的最短路徑長度不大於從源點到V中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點距離就是從源點到此頂點的最短路徑長度，V中的頂點距離是從源點到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。

Ⅲ 基於激光雷達的SLAM和路徑規劃演算法研究與實現

本文僅供學習使用，並非商業用途，全文是針對哈爾濱工業大學劉文之的論文《移動機器人的路徑規劃與定位技術研究》進行提煉與學習。論文來源中國知網，引用格式如下：
[1]劉文之. 基於激光雷達的SLAM和路徑規劃演算法研究與實現[D].哈爾濱工業大學,2018.

相關坐標系轉換原理已經在前一篇文章寫完了，直接上轉換方程。

這里他的運動模型選擇的是基於里程計的運動模型，還有一種基於速度的運動模型，其實都差不多，整體思想都一樣。里程計是通過計算一定時間內光電編碼器輸出脈沖數來估計機器人運動位移的裝置，主要是使用光電碼盤。根據光電碼盤計算出此時輪子的速度，然後通過已知的輪子半徑來獲得單位時間 每個輪子 的位移增量。

高等數學可知單位時間位移增量就是速度，對速度在一定時間上進行積分就得到這一段時間所走過的路程。

根據上圖，我們可以求出來機器人航向角角速度、圓弧運動半徑和機器人角度變化量，由此可以解的機器人在當前時刻的位姿。

實際上也是有誤差，所以單獨依靠里程計會與實際結果產生較大誤差，所以必須引入其他的外部感測器對外部環境的觀測來修正這些誤差，從而提高定位精度。

首先肯定需要將激光雷達所測得的端點坐標從極坐標、機器人坐標中轉換到世界坐標中。

這張略過，暫時不需要看這個

路徑規劃演算法介紹：

因為該演算法會產生大量的無用臨時途徑，簡單說就是很慢，所以有了其他演算法。

了解兩種代價之後，對於每一個方塊我們採用預估代價與當前路徑代價相加的方法，這樣可以表示每一個路徑點距離終點的距離。在BFS搜索過程的基礎上，優先挑選總代價最低的那個路徑進行搜索，就可以少走不少彎路。（演算法講解 https://www.bilibili.com/video/BV1bv411y79P?from=search&seid=3623681329596549549 ）

在局部路徑規劃演算法之中，我們選用DWA演算法（dynamic window approach），又叫動態窗口法。動態窗口法主要是在速度(v, w)空間中采樣多組速度，並模擬機器人在這些速度下一定時間內的軌跡。在得到多組軌跡後，對這些軌跡進行評價，選取最優的軌跡所對應的速度來驅動機器人運動。
state sampling就是按照之前給出的全局路徑規劃，無論是Dijkstra還是A* 都可以方便的得到state sampling，DWA演算法所需要提前建立的action sampling有兩種：

但是無論是什麼情況，上述所做的工作就是把機器人的位移轉化到世界坐標中來，而不是機器人坐標系。速度采樣結束之後，只需要對小車的軌跡進行評判，就可以得到最優解了。下面介紹速度采樣的辦法。

對速度進行采樣一般有以下三個限制：

當確定了速度范圍之後，就需要根據速度解析度來對小車速度離散化，在每一時刻將小車在不同直線速度角速度組合下所即將要行駛的距離都可視化出來。

其中每一條軌跡都是很多小直線連接起來的。

需要用評價函數來對上述軌跡進行選擇，選擇最適合的軌跡

最後為了讓三個參數在評價函數里所發揮的作用均等，我們使用歸一化處理來計算權重。

演算法流程整體如下：

Ⅳ vc環境 最短路徑演算法

單源最短路徑演算法---Dijkstra演算法
轉自:http://space.flash8.net/space/html/07/14107_itemid_400760.html

演算法介紹
Dijkstra演算法是由荷蘭計算機科學家艾茲格·迪科斯徹發現的。演算法解決的是有向圖中最短路徑問題。

舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離。 Dijkstra演算法可以用來找到兩個城市之間的最短路徑。

Dijkstra 演算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。我們以V表示G中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。 (u,v)表示從頂點u到v有路徑相連。我們以E所有邊的集合，而邊的權重則由權重函數w: E → [0, ∞]定義。因此，w(u,v)就是從頂點u到頂點v的非負花費值(cost)。邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑 上所有邊的花費值總和。已知有V中有頂點s及t，Dijkstra演算法可以找到s到t的最低花費路徑(i.e. 最短路徑)。這個演算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑。

演算法描述
這個演算法是通過為每個頂點v保留目前為止所找到的從s到v的最短路徑來工作的。 初始時，源點s的路徑長度值被賦為0（d[s]=0），同時把所有其他頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑（對於V中所有 頂點v除s外d[v]= ∞）。當演算法結束時，d[v]中儲存的便是從s到v的最短路徑，或者如果路徑不存在的話是無窮大。 Dijstra演算法的基礎操作是邊的拓展：如果存在一條從u到v的邊，那麼從s到u的最短路徑可以通過將邊(u,v)添加到尾部來拓展一條從s到v的路 徑。這條路徑的長度是d[u]+w(u,v)。如果這個值比目前已知的d[v]的值要小，我們可以用新值來替代當前d[v]中的值。拓展邊的操作一直執行 到所有的d[v]都代表從s到v最短路徑的花費。這個演算法經過組織因而當d[u]達到它最終的值的時候沒條邊(u,v)都只被拓展一次。

演算法維護兩個頂點集S和Q。集合S保留了我們已知的所有d[v]的值已經是最短路徑的值頂點，而集合Q則保留其他所有頂點。集合S初始狀態為空，而後每一步 都有一個頂點從Q移動到S。這個被選擇的頂點是Q中擁有最小的d[u]值的頂點。當一個頂點u從Q中轉移到了S中，演算法對每條外接邊(u,v)進行拓展。

偽碼
在下面的演算法中,u:=Extract_Min(Q)在在頂點集Q中搜索有最小的d[u]值的頂點u。這個頂點被從集合Q中刪除並返回給用戶。

function Dijkstra(G, w, s)

// 初始化
for each vertex v in V[G] {
d[v] := infinity
previous[v] := undefined
d[s] := 0
}

S := empty set
Q := set of all vertices

while Q is not an empty set { // Dijstra演算法主體
u := Extract_Min(Q)
S := S union {u}
for each edge (u,v) outgoing from u
if d[v] > d[u] + w(u,v) // 拓展邊(u,v)
d[v] := d[u] + w(u,v)
previous[v] := u
}

如果我們只對在s和t之間尋找一條最短路徑的話，我們可以在第9行添加條件如果滿足u=t的話終止程序。

現在我們可以通過迭代來回溯出s到t的最短路徑

1 S := empty sequence
2 u := t
3 while defined u
4 insert u to the beginning of S
5 u := previous[u]

現在序列S就是從s到t的最短路徑的頂點集.

時間復雜度
我們可以用大O符號將Dijkstra演算法的運行時間表示為邊數m和頂點數n的函數。

Dijkstra演算法最簡單的實現方法是用一個鏈表或者數組來存儲所有頂點的集合Q,所以搜索Q中最小元素的運算(Extract-Min(Q))只需要線性搜索Q中的所有元素。這樣的話演算法的運行時間是O(n2)。

對 於邊數少於n2稀疏圖來說，我們可以用鄰接表來更有效的實現Dijkstra演算法。同時需要將一個二叉堆或者斐波納契堆用作優先隊列來尋找最小的頂點 (Extract-Min)。當用到二叉堆的時候，演算法所需的時間為O((m+n)log n)，斐波納契堆能稍微提高一些性能，讓演算法運行時間達到O(m + n log n)。

相關問題和演算法
在Dijkstra 演算法的基礎上作一些改動，可以擴展其功能。例如，有時希望在求得最短路徑的基礎上再列出一些次短的路徑。為此，可先在原圖上計算出最短路徑，然後從圖中刪 去該路徑中的某一條邊，在餘下的子圖中重新計算最短路徑。對於原最短路徑中的每一條邊，均可求得一條刪去該邊後子圖的最短路徑，這些路徑經排序後即為原圖 的一系列次短路徑。

OSPF（open shortest path first, 開放最短路徑優先）演算法是Dijkstra演算法在網路路由中的一個具體實現。

與Dijkstra演算法不同，Bellman-Ford演算法可用於具有負花費邊的圖，只要圖中不存在總花費為負值且從源點 s 可達的環路（如果有這樣的環路，則最短路徑不存在，因為沿環路循環多次即可無限制的降低總花費）。

與最短路徑問題有關的一個問題是旅行商問題(traveling salesman problem)，它要求找出通過所有頂點恰好一次且最終回到源點的最短路徑。該問題是NP難的；換言之，與最短路徑問題不同，旅行商問題不太可能具有多項式時間演算法。

如果有已知信息可用來估計某一點到目標點的距離，則可改用A*演算法 ，以減小最短路徑的搜索范圍。

另外，用於解決最短路徑問題的演算法被稱做「最短路徑演算法」， 有時被簡稱作「路徑演算法」。 最常用的路徑演算法有：
Dijkstra演算法
A*演算法
SPFA演算法
Bellman-Ford演算法
Floyd-Warshall演算法
Johnson演算法
所謂單源最短路徑問題是指：已知圖G＝（V，E），我們希望找出從某給定的源結點S∈V到V中的每個結點的最短路徑。
首先，我們可以發現有這樣一個事實：如果P是G中從vs到vj的最短路，vi是P中的一個點，那麼，從vs沿P到vi的路是從vs到vi的最短路。

Ⅳ 數學建模中，給出非常多的節點，求這些節點的最短路徑（類似一條線的路徑），應該用什麼演算法好

下面是我自己編寫的一段代碼，用來求過包含兩千多個點的最短路，速度很快，比遺傳、蟻群快而且最短路更短。你可以試試看，有問題再問我。
function [S,len]=short(P)
% 此程序用來求相同類型點間的最短路
% P表示某一類型的點的坐標矩陣
% p是最短路徑
% d是路徑權值和
%建立權值矩陣
n=length(P);%求該類型點的數量
W=zeros(n,n);
for i=1:n %計算權值並填充權值矩陣,由於各點聯通，此權值矩陣就是該圖的最短路矩陣
for j=(i+1):n
W(i,j)=sqrt((P(i,1)-P(j,1))^2+(P(i,2)-P(j,2))^2);
end
end
for i=2:n
for j=1:(i-1)
W(i,j)=W(j,i);
end
end
%求通過所有點的最短路
%先求從i點至j點，必須通過指定其他n-2個點的最短路,選出其中的的最短路
S=zeros(1,n);
S(1)=1; %先插入1,2點，以此為基準，每次插進一個新點
S(2)=2;
d1=2*W(1,2);
for i=3:n %新加入的點的標號
d1i=zeros(1,i); %插入第i個點，有i中可能的距離,其中最小值將為該輪的d1
for j=1:i %新加入點的位置，插入第i個點是有i個空位可供選擇
if j==1 %在第一個空位插入
d1i(j)=d1+W(i,S(1))+W(i,S(i-1))-W(S(1),S(i-1)); %插入點在首端時，距離為原距離與第i點與上一次插入後的第1位置的點之間距離之和
end
if j>1 & j<i %在中間的空位插入
d1i(j)=d1+W(S(j-1),i)+W(i,S(j))-W(S(j-1),S(j));
end
if j==i
d1i(j)=d1+W(S(i-1),i)+W(S(1),i)-W(S(1),S(i-1));
end
end
[d1,I]=min(d1i);
S((I+1):i)=S(I:(i-1)); %將第I位後面的點後移一位
S(I)=i;%將第i點插入在I位置
end
len=d1;

下面這段代碼是我用來把上面的結果保存到txt文件中的代碼，如果你需要，可以用用。代碼是我上次用過的沒有改，你自己按照需要自己改吧。
clear
close all
clc
loaddata
X=[C;E;I;J];
[S,len]=short(X);
DrawPath(S,X);
print(1,'-dpng','cmeiju3.png');
% 將結果保存至txt文件
fid=fopen('cmeijulujin.txt','wt'); %創建alunjin.txt文件
fprintf(fid,'c號刀具\n');
fprintf(fid,'%d %d\n',X(S));
save('cmeijus','S');
save('cmeijulen','len');

Ⅵ 蟻群演算法是什麼

蟻群演算法，又稱螞蟻演算法，是一種用來在圖中尋找優化路徑的機率型演算法。 它由Marco Dorigo於1992年在他的博士論文中提出，其靈感來源於螞蟻在尋找食物過程中發現路徑的行為。蟻群演算法是一種模擬進化演算法，初步的研究表明該演算法具有許多優良的性質。針對PID控制器參數優化設計問題，將蟻群演算法設計的結果與遺傳演算法設計的結果進行了比較，數值模擬結果表明，蟻群演算法具有一種新的模擬進化優化方法的有效性和應用價值。

原理
設想，如果我們要為螞蟻設計一個人工智慧的程序，那麼這個程序要多麼復雜呢？首先，你要讓螞蟻能夠避開障礙物，就必須根據適當的地形給它編進指令讓他們能夠巧妙的避開障礙物，其次，要讓螞蟻找到食物，就需要讓他們遍歷空間上的所有點；再次，如果要讓螞蟻找到最短的路徑，那麼需要計算所有可能的路徑並且比較它們的大小，而且更重要的是，你要小心翼翼地編程，因為程序的錯誤也許會讓你前功盡棄。這是多麼不可思議的程序！太復雜了，恐怕沒人能夠完成這樣繁瑣冗餘的程序。

然而，事實並沒有你想得那麼復雜，上面這個程序每個螞蟻的核心程序編碼不過100多行！為什麼這么簡單的程序會讓螞蟻干這樣復雜的事情？答案是：簡單規則的涌現。事實上，每隻螞蟻並不是像我們想像的需要知道整個世界的信息，他們其實只關心很小范圍內的眼前信息，而且根據這些局部信息利用幾條簡單的規則進行決策，這樣，在蟻群這個集體里，復雜性的行為就會凸現出來。這就是人工生命、復雜性科學解釋的規律！那麼，這些簡單規則是什麼呢？

Ⅶ 計算機網路的最短路徑演算法有哪些對應哪些協議

用於解決最短路徑問題的演算法被稱做「最短路徑演算法」，有時被簡稱作「路徑演算法」。最常用的路徑演算法有：
Dijkstra演算法、A*演算法、SPFA演算法、Bellman-Ford演算法和Floyd-Warshall演算法，本文主要介紹其中的三種。

最短路徑問題是圖論研究中的一個經典演算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。
演算法具體的形式包括：

確定起點的最短路徑問題：即已知起始結點，求最短路徑的問題。

確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。
確定起點終點的最短路徑問題：即已知起點和終點，求兩結點之間的最短路徑。

全局最短路徑問題：求圖中所有的最短路徑。
Floyd

求多源、無負權邊的最短路。用矩陣記錄圖。時效性較差，時間復雜度O(V^3)。

Floyd-Warshall演算法（Floyd-Warshall algorithm）是解決任意兩點間的最短路徑的一種演算法，可以正確處理有向圖或負權的最短路徑問題。
Floyd-Warshall演算法的時間復雜度為O(N^3)，空間復雜度為O(N^2)。

Floyd-Warshall的原理是動態規劃：

設Di,j,k為從i到j的只以(1..k)集合中的節點為中間節點的最短路徑的長度。

若最短路徑經過點k，則Di,j,k = Di,k,k-1 + Dk,j,k-1；

若最短路徑不經過點k，則Di,j,k = Di,j,k-1。

因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。

在實際演算法中，為了節約空間，可以直接在原來空間上進行迭代，這樣空間可降至二維。

Floyd-Warshall演算法的描述如下：

for k ← 1 to n do

for i ← 1 to n do

for j ← 1 to n do

if (Di,k + Dk,j < Di,j) then

Di,j ← Di,k + Dk,j;

其中Di,j表示由點i到點j的代價，當Di,j為 ∞ 表示兩點之間沒有任何連接。

Dijkstra

求單源、無負權的最短路。時效性較好，時間復雜度為O（V*V+E）,可以用優先隊列進行優化，優化後時間復雜度變為0（v*lgn）。
源點可達的話，O（V*lgV+E*lgV）=>O（E*lgV）。

當是稀疏圖的情況時，此時E=V*V/lgV，所以演算法的時間復雜度可為O（V^2） 。可以用優先隊列進行優化，優化後時間復雜度變為0（v*lgn）。
Bellman-Ford

求單源最短路，可以判斷有無負權迴路（若有，則不存在最短路），時效性較好，時間復雜度O（VE）。

Bellman-Ford演算法是求解單源最短路徑問題的一種演算法。

單源點的最短路徑問題是指：給定一個加權有向圖G和源點s，對於圖G中的任意一點v，求從s到v的最短路徑。

與Dijkstra演算法不同的是，在Bellman-Ford演算法中，邊的權值可以為負數。設想從我們可以從圖中找到一個環

路（即從v出發，經過若干個點之後又回到v）且這個環路中所有邊的權值之和為負。那麼通過這個環路，環路中任意兩點的最短路徑就可以無窮小下去。如果不處理這個負環路，程序就會永遠運行下去。 而Bellman-Ford演算法具有分辨這種負環路的能力。
SPFA

是Bellman-Ford的隊列優化，時效性相對好，時間復雜度O（kE）。（k< 與Bellman-ford演算法類似，SPFA演算法採用一系列的鬆弛操作以得到從某一個節點出發到達圖中其它所有節點的最短路徑。所不同的是，SPFA演算法通過維護一個隊列，使得一個節點的當前最短路徑被更新之後沒有必要立刻去更新其他的節點，從而大大減少了重復的操作次數。
SPFA演算法可以用於存在負數邊權的圖，這與dijkstra演算法是不同的。

與Dijkstra演算法與Bellman-ford演算法都不同，SPFA的演算法時間效率是不穩定的，即它對於不同的圖所需要的時間有很大的差別。
在最好情形下，每一個節點都只入隊一次，則演算法實際上變為廣度優先遍歷，其時間復雜度僅為O(E)。另一方面，存在這樣的例子，使得每一個節點都被入隊(V-1)次，此時演算法退化為Bellman-ford演算法，其時間復雜度為O(VE)。
SPFA演算法在負邊權圖上可以完全取代Bellman-ford演算法，另外在稀疏圖中也表現良好。但是在非負邊權圖中，為了避免最壞情況的出現，通常使用效率更加穩定的Dijkstra演算法，以及它的使用堆優化的版本。通常的SPFA。

Ⅷ 蟻群演算法的概念，最好能舉例說明一些蟻群演算法適用於哪些問題！

概念：蟻群演算法(ant colony optimization, ACO)，又稱螞蟻演算法，是一種用來在圖中尋找優化路徑的機率型演算法。它由Marco Dorigo於1992年在他的博士論文中提出，其靈感來源於螞蟻在尋找食物過程中發現路徑的行為。蟻群演算法是一種模擬進化演算法,初步的研究表明該演算法具有許多優良的性質.針對PID控制器參數優化設計問題,將蟻群演算法設計的結果與遺傳演算法設計的結果進行了比較,數值模擬結果表明,蟻群演算法具有一種新的模擬進化優化方法的有效性和應用價值

其原理：為什麼小小的螞蟻能夠找到食物？他們具有智能么？設想，如果我們要為螞蟻設計一個人工智慧的程序，那麼這個程序要多麼復雜呢？首先，你要讓螞蟻能夠避開障礙物，就必須根據適當的地形給它編進指令讓他們能夠巧妙的避開障礙物，其次，要讓螞蟻找到食物，就需要讓他們遍歷空間上的所有點；再次，如果要讓螞蟻找到最短的路徑，那麼需要計算所有可能的路徑並且比較它們的大小，而且更重要的是，你要小心翼翼的編程，因為程序的錯誤也許會讓你前功盡棄。這是多麼不可思議的程序！太復雜了，恐怕沒人能夠完成這樣繁瑣冗餘的程序

應用范圍：螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數為速度半徑（一般是3），那麼它能觀察到的范圍就是3*3個方格世界，並且能移動的距離也在這個范圍之內

引申：跟著螞蟻的蹤跡，你找到了什麼？通過上面的原理敘述和實際操作，我們不難發現螞蟻之所以具有智能行為，完全歸功於它的簡單行為規則，而這些規則綜合起來具有下面兩個方面的特點： 1、多樣性 2、正反饋 多樣性保證了螞蟻在覓食的時候不置走進死胡同而無限循環，正反饋機制則保證了相對優良的信息能夠被保存下來。我們可以把多樣性看成是一種創造能力，而正反饋是一種學習強化能力。正反饋的力量也可以比喻成權威的意見，而多樣性是打破權威體現的創造性，正是這兩點小心翼翼的巧妙結合才使得智能行為涌現出來了。 引申來講，大自然的進化，社會的進步、人類的創新實際上都離不開這兩樣東西，多樣性保證了系統的創新能力，正反饋保證了優良特性能夠得到強化，兩者要恰到好處的結合。如果多樣性過剩，也就是系統過於活躍，這相當於螞蟻會過多的隨機運動，它就會陷入混沌狀態；而相反，多樣性不夠，正反饋機制過強，那麼系統就好比一潭死水。這在蟻群中來講就表現為，螞蟻的行為過於僵硬，當環境變化了，螞蟻群仍然不能適當的調整。 既然復雜性、智能行為是根據底層規則涌現的，既然底層規則具有多樣性和正反饋特點，那麼也許你會問這些規則是哪裡來的？多樣性和正反饋又是哪裡來的？我本人的意見：規則來源於大自然的進化。而大自然的進化根據剛才講的也體現為多樣性和正反饋的巧妙結合。而這樣的巧妙結合又是為什麼呢？為什麼在你眼前呈現的世界是如此栩栩如生呢？答案在於環境造就了這一切，之所以你看到栩栩如生的世界，是因為那些不能夠適應環境的多樣性與正反饋的結合都已經死掉了，被環境淘汰了！ 蟻群演算法的實現 下面的程序開始運行之後，螞蟻們開始從窩里出動了，尋找食物；他們會順著屏幕爬滿整個畫面，直到找到食物再返回窩。 其中，『F』點表示食物，『H』表示窩，白色塊表示障礙物，『+』就是螞蟻了。

具體參考http://ke..com/view/539346.htm
希望對你有幫助，謝謝。