最短路問題的演算法

㈠ 求最短路問題的三種演算法並說明使用條件

現在比較常用的最短路演算法是dijkstra它的使用條件是你會寫，且圖中無負權邊

SPFA是現在稀疏圖上常用最短路演算法，且無負環，而且你要會寫
floyd是當前求多源最短路的常用演算法
對於程序猿來說，dijkstra性能穩定比較changyong
對於oier來說，只要不是稠密圖，一定寫spfa，因為spfa在稀疏圖上太快了

㈡ 最短路徑演算法

最短路徑的演算法主要有三種：floyd演算法、Dijkstra演算法、Bellman-Ford(貝爾曼-福特)

一、floyd演算法

基本思想如下：從任意節點A到任意節點B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經過若干個節點X到B。所以，我們假設Dis(AB)為節點A到節點B的最短路徑的距離，對於每一個節點X，我們檢查Dis(AX) + Dis(XB) < Dis(AB)是否成立，如果成立，證明從A到X再到B的路徑比A直接到B的路徑短，我們便設置Dis(AB) = Dis(AX) + Dis(XB)，這樣一來，當我們遍歷完所有節點X，Dis(AB)中記錄的便是A到B的最短路徑的距離。

三、Bellman-Ford(貝爾曼-福特)

演算法的流程如下：

給定圖G(V, E)（其中V、E分別為圖G的頂點集與邊集），源點s，

1.數組Distant[i]記錄從源點s到頂點i的路徑長度，初始化數組Distant[n]為, Distant[s]為0；

2.以下操作循環執行至多n-1次，n為頂點數：
對於每一條邊e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，則另Distant[v] = Distant[u]+w(u, v)。w(u, v)為邊e(u,v)的權值；
若上述操作沒有對Distant進行更新，說明最短路徑已經查找完畢，或者部分點不可達，跳出循環。否則執行下次循環；

3.為了檢測圖中是否存在負環路，即權值之和小於0的環路。對於每一條邊e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的邊，則圖中存在負環路，即是說該圖無法求出單源最短路徑。否則數組Distant[n]中記錄的就是源點s到各頂點的最短路徑長度。

可知，Bellman-Ford演算法尋找單源最短路徑的時間復雜度為O(V*E).

㈢ 最短路徑演算法

Dijkstra演算法，A*演算法和D*演算法

Dijkstra演算法是典型最短路演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。

Dijkstra演算法是很有代表性的最短路演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。

Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式，Drew為了和下面要介紹的 A* 演算法和 D* 演算法表述一致，這里均採用OPEN,CLOSE表的方式。

大概過程：
創建兩個表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
1． 訪問路網中里起始點最近且沒有被檢查過的點，把這個點放入OPEN組中等待檢查。
2． 從OPEN表中找出距起始點最近的點，找出這個點的所有子節點，把這個點放到CLOSE表中。
3． 遍歷考察這個點的子節點。求出這些子節點距起始點的距離值，放子節點到OPEN表中。
4． 重復2，3，步。直到OPEN表為空，或找到目標點。

提高Dijkstra搜索速度的方法很多，常用的有數據結構採用Binary heap的方法，和用Dijkstra從起始點和終點同時搜索的方法。

A*（A-Star)演算法是一種啟發式演算法，是靜態路網中求解最短路最有效的方法。

公式表示為： f(n)=g(n)+h(n),
其中f(n) 是節點n從初始點到目標點的估價函數，
g(n) 是在狀態空間中從初始節點到n節點的實際代價，
h(n)是從n到目標節點最佳路徑的估計代價。

保證找到最短路徑（最優解的）條件，關鍵在於估價函數h(n)的選取：
估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。
如果 估價值>實際值, 搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。
估價值與實際值越接近，估價函數取得就越好。
例如對於幾何路網來說，可以取兩節點間歐幾理德距離（直線距離）做為估價值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；這樣估價函數f在g值一定的情況下，會或多或少的受估價值h的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。明顯優於Dijstra演算法的毫無無方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索過程：
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,->算X的估價值->
While(OPEN!=NULL)
{
從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
else
{
if(X in OPEN) 比較兩個X的估價值f //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於OPEN表的估價值 )
更新OPEN表中的估價值; //取最小路徑的估價值
if(X in CLOSE) 比較兩個X的估價值 //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於CLOSE表的估價值 )
更新CLOSE表中的估價值; 把X節點放入OPEN //取最小路徑的估價值
if(X not in both)
求X的估價值;
並將X插入OPEN表中; //還沒有排序
}
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
}

A*演算法和Dijistra演算法的區別在於有無估價值，Dijistra演算法相當於A*演算法中估價值為0的情況。

動態路網，最短路演算法 D*A* 在靜態路網中非常有效（very efficient for static worlds），但不適於在動態路網，環境如權重等不斷變化的動態環境下。

D*是動態A*（D-Star,Dynamic A*） 卡內及梅隆機器人中心的Stentz在1994和1995年兩篇文章提出，主要用於機器人探路。是火星探測器採用的尋路演算法。

主要方法：
1.先用Dijstra演算法從目標節點G向起始節點搜索。儲存路網中目標點到各個節點的最短路和該位置到目標點的實際值h,k（k為所有變化h之中最小的值,當前為k=h。每個節點包含上一節點到目標點的最短路信息1(2),2(5),5(4)，4（7）。則1到4的最短路為1-2-5-4。
原OPEN和CLOSE中節點信息保存。
2.機器人沿最短路開始移動，在移動的下一節點沒有變化時，無需計算，利用上一步Dijstra計算出的最短路信息從出發點向後追述即可，當在Y點探測到下一節點X狀態發生改變，如堵塞。機器人首先調整自己在當前位置Y到目標點G的實際值h(Y)，h(Y)=X到Y的新權值c(X,Y)+X的原實際值h(X).X為下一節點(到目標點方向Y->X->G），Y是當前點。k值取h值變化前後的最小。
3.用A*或其它演算法計算，這里假設用A*演算法,遍歷Y的子節點，點放入CLOSE,調整Y的子節點a的h值，h(a)=h(Y)+Y到子節點a的權重C(Y,a),比較a點是否存在於OPEN和CLOSE中，方法如下：
while()
{
從OPEN表中取k值最小的節點Y;
遍歷Y的子節點a,計算a的h值 h(a)=h(Y)+Y到子節點a的權重C(Y,a)
{
if(a in OPEN) 比較兩個a的h值
if( a的h值小於OPEN表a的h值 )
{ 更新OPEN表中a的h值;k值取最小的h值
有未受影響的最短路經存在
break;
}
if(a in CLOSE) 比較兩個a的h值 //注意是同一個節點的兩個不同路徑的估價值
if( a的h值小於CLOSE表的h值 )
{
更新CLOSE表中a的h值; k值取最小的h值;將a節點放入OPEN表
有未受影響的最短路經存在
break;
}
if(a not in both)
將a插入OPEN表中; //還沒有排序
}
放Y到CLOSE表；
OPEN表比較k值大小進行排序；
}
機器人利用第一步Dijstra計算出的最短路信息從a點到目標點的最短路經進行。

D*演算法在動態環境中尋路非常有效，向目標點移動中，只檢查最短路徑上下一節點或臨近節點的變化情況，如機器人尋路等情況。對於距離遠的最短路徑上發生的變化，則感覺不太適用。

㈣ 求最短路徑演算法有哪幾種

Dijkstra演算法，A*演算法和D*演算法

Dijkstra演算法是典型最短路演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。

Dijkstra演算法是很有代表性的最短路演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。

Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式，Drew為了和下面要介紹的 A* 演算法和 D* 演算法表述一致，這里均採用OPEN,CLOSE表的方式

㈤ 圖論：最短路演算法有哪些以及它們的比較

弗洛伊德 n^3 的時間把n個點兩兩的最短路求出來
迪傑斯特拉 n^2的時間(用堆優化到Nlog(M),M是邊數)，單源最短路，但是不能對付有負權的圖
SPFA，M*k的時間（K是一個常數），單源最短路，能對付有負權的圖
感覺常用的就這三個了吧。。

㈥ C語言實現最短路問題的演算法

＃i nclude<stdio.h>
＃i nclude <stdlib.h>
//Dijkstra演算法實現函數
void Dijkstra(int n,int v,int dist[],int prev[],int **cost)
{
int i;
int j;
int maxint = 65535;//定義一個最大的數值，作為不相連的兩個節點的代價權值
int *s ;//定義具有最短路徑的節點子集s
s = (int *)malloc(sizeof(int) * n);
//初始化最小路徑代價和前一跳節點值
for (i = 1; i <= n; i++)
{
dist[i] = cost[v][i];
s[i] = 0;
if (dist[i] == maxint)
{
prev[i] = 0;
}
else
{
prev[i] = v;
}
}
dist[v] = 0;
s[v] = 1;//源節點作為最初的s子集
for (i = 1; i < n; i++)
{
int temp = maxint;
int u = v;
//加入具有最小代價的鄰居節點到s子集
for (j = 1; j <= n; j++)
{
if ((!s[j]) && (dist[j] < temp))
{
u = j;
temp = dist[j];
}
}
s[u] = 1;
//計算加入新的節點後，更新路徑使得其產生代價最短
for (j = 1; j <= n; j++)
{
if ((!s[j]) && (cost[u][j] < maxint))
{
int newdist = dist[u] + cost[u][j];
if (newdist < dist[j])
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}
}
//展示最佳路徑函數
void ShowPath(int n,int v,int u,int *dist,int *prev)
{
int j = 0;
int w = u;
int count = 0;
int *way ;
way=(int *)malloc(sizeof(int)*(n+1));
//回溯路徑
while (w != v)
{
count++;
way[count] = prev[w];
w = prev[w];
}
//輸出路徑
printf("the best path is:\n");
for (j = count; j >= 1; j--)
{
printf("%d -> ",way[j]);
}
printf("%d\n",u);
}
//主函數，主要做輸入輸出工作
void main()
{
int i,j,t;
int n,v,u;

int **cost;//代價矩陣
int *dist;//最短路徑代價
int *prev;//前一跳節點空間
printf("please input the node number: ");
scanf("%d",&n);
printf("please input the cost status:\n");

cost=(int **)malloc(sizeof(int)*(n+1));
for (i = 1; i <= n; i++)
{
cost[i]=(int *)malloc(sizeof(int)*(n+1));
}
//輸入代價矩陣
for (j = 1; j <= n; j++)
{
for (t = 1; t <= n; t++)
{
scanf("%d",&cost[j][t]);
}
}

dist = (int *)malloc(sizeof(int)*n);
prev = (int *)malloc(sizeof(int)*n);
printf("please input the source node: ");
scanf("%d",&v);
//調用dijkstra演算法
Dijkstra(n, v, dist, prev, cost);
printf("*****************************\n");
printf("have confirm the best path\n");
printf("*****************************\n");
for(i = 1; i <= n ; i++)
{
if(i!=v)
{
printf("the distance cost from node %d to node %d is %d\n",v,i,dist[i]);
printf("the pre-node of node %d is node %d \n",i,prev[i]);
ShowPath(n,v,i, dist, prev);
}
}
}

㈦ 求A到B之間的最短路徑，怎麼獲取

問題：從某頂點出發，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑——最短路徑。解決最短路的問題有以下演算法，Dijkstra演算法，Bellman-Ford演算法，Floyd演算法和SPFA演算法，另外還有著名的啟發式搜索演算法A*，不過A*准備單獨出一篇，其中Floyd演算法可以求解任意兩點間的最短路徑的長度。任意一個最短路演算法都是基於這樣一個事實：從任意節點A到任意節點B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經過若干個節點到B。
(1) 迪傑斯特拉(Dijkstra)演算法按路徑長度(看下面表格的最後一行，就是next點)遞增次序產生最短路徑。先把V分成兩組：
S：已求出最短路徑的頂點的集合
V-S=T：尚未確定最短路徑的頂點集合
將T中頂點按最短路徑遞增的次序加入到S中，依據：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的直接路徑的權值或是從V0經S中頂點到Vk的路徑權值之和（反證法可證，說實話，真不明白哦）。
(2) 求最短路徑步驟
初使時令 S={V0},T={其餘頂點}，T中頂點對應的距離值， 若存在<V0,Vi>，為<V0,Vi>弧上的權值（和SPFA初始化方式不同），若不存在<V0,Vi>，為Inf。
從T中選取一個其距離值為最小的頂點W(貪心體現在此處)，加入S(注意不是直接從S集合中選取，理解這個對於理解vis數組的作用至關重要)，對T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值（上面兩個並列for循環，使用最小點更新）。
重復上述步驟，直到S中包含所有頂點，即S=V為止（說明最外層是除起點外的遍歷）。

㈧ 節約里程法求解最短路問題

你只要記住2點之間直線最短。
節約里程法是用來解決運輸車輛數目不確定的問題的最有名的啟發式演算法。

1、節約里程法優化過程分為並行方式和串列方式兩種。核心思想是依次將運輸問題中的兩個迴路合並為一個迴路，每次使合並後的總運輸距離減小的幅度最大，直到達到一輛車的裝載限制時，再進行下一輛車的優化。

2、節約里程法最短路徑是兩點之間直線最短。最短路徑是典型的最短路徑路由演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。

3、在路徑優化問題還包括節約里程法，遺傳演算法，神經網路這幾種演算法。其中遺傳演算法相對簡便，由於遺傳演算法不能直接處理問題空間的參數,因此必須通過編碼將要求解的問題表示成遺傳空間的染色體或者個體。這一轉換操作就叫做編碼。

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

用於解決最短路徑問題的演算法被稱做「最短路徑演算法」，有時被簡稱作「路徑演算法」。最常用的路徑演算法有：
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。

㈩ 圖論中常見的最短路徑演算法有幾種都是什麼

主要是有三種、、
第一種是最直接的貪心dijkstra演算法、、可以利用堆數據結構進行優化、、缺點就是不能求有負權的最短路與判斷負環、、
第二種是bellman-ford演算法、、根據鬆弛操作的性質是可以來判斷負環的、、時間復雜度是O(nm)的、、
第三種是SPFA演算法、、把他單獨拿出來作為一種演算法並不是非常好的、、他的實質應該是上面的bellman-ford演算法的隊列優化時間復雜度更低、O(KE)、K的值約等於2、、