求最短路徑的演算法
『壹』 求最短路徑演算法
java">importjava.awt.*;
importjava.util.HashSet;
importjava.util.Random;
classexample2{
privatestaticPoint[]mTestPoints;
//已知平面上N點坐標,求遍歷所有點的最短路徑.
publicstaticvoidmain(String[]args){
//兩點之間的距離d=√(a^2+b^2)其中a=|x1–x2|;b=|y1-y2|
//都是簡單的正相關函數,距離最短那麼需要a+b最小
//n個點需要求C(n,2)次
//其實java提供了兩點之間距離的Api咱們直接使用即可
generateTestPoints();
doubleminDistance=Double.MAX_VALUE;
for(inti=0;i<mTestPoints.length;i++){
//兩兩計算,數組中每個點只跟後面的點求距離
for(intj=i+1;j<mTestPoints.length;j++){
doubledistance=mTestPoints[i].distance(mTestPoints[j]);
if(distance<minDistance){
minDistance=distance;
}
}
}
//得到結果
System.out.println("最短距離為:"+minDistance);
}
(){
//隨機生成10個點的集合,為了去重使用hashSet
Randomrandom=newRandom();
HashSet<Point>mPointSet=newHashSet<>();
for(inti=0;i<10;i++){
booleanadd=mPointSet.add(newPoint(random.nextInt(100),random.nextInt(100)));
if(!add){
--i;
}
}
mTestPoints=mPointSet.toArray(newPoint[10]);
}
}
『貳』 最短路徑演算法
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*演算法在動態環境中尋路非常有效，向目標點移動中，只檢查最短路徑上下一節點或臨近節點的變化情況，如機器人尋路等情況。對於距離遠的最短路徑上發生的變化，則感覺不太適用。
『叄』 迪傑斯特拉演算法求最短路徑題怎麼做
最早的路徑題，這個在做的時候，你可以通過練習一個函數關系式就能夠進行，把它簡單的測量出來的還是比較簡單的。
『肆』 Flody演算法 求最短路徑的求解過程
你好。
很幸運看到你的問題。
但是又很遺憾到現在還沒有人回答你的問題。也可能你現在已經在別的地方找到了答案，那就得恭喜你啦。
可能是你問的問題有些專業了，沒人會。或者別人沒有遇到或者接觸過你的問題，所以幫不了你。建議你去問題的相關論壇去求助，那裡的人通常比較多，也比較熱心，可能能快點幫你解決問題。
希望我的回答也能夠幫到你！
祝你好運~！
『伍』 求一個最短路徑的演算法
以前看到過，貼給你
Private Function OrderXY(X() As Double, Y() As Double)
Dim i, j, k, m, n, num, temp As Double
Dim NewX() As Double
Dim NewY() As Double
Dim Smin As Double '定義最短總距離
If UBound(X()) <> UBound(Y()) Then MsgBox "坐標錯誤": Exit Function '防止數據錯誤
n = UBound(X())
ReDim p(n) As Long
p(0) = 0: num = 1
For i = 1 To n
p(i) = i 'p()數組依次存儲從0到n共n+1個數
num = num * i '計算num，num表示的是n個坐標（除X(0),Y(0)以外)共有n！種排列
Next
ReDim Stance(num - 1) As Double '定義數組存儲每種連接方法的總距離
ReDim NewX(n)
ReDim NewY(n)
For i = 0 To n - 1 'Stance（0）是按照原坐標順序依次連接的總距離
Stance(0) = Stance(0) + Sqr((Y(i + 1) - Y(i)) * (Y(i + 1) - Y(i)) + (X(i + 1) - X(i)) * (X(i + 1) - X(i)))
Next
Smin = Stance(0)
For k = 0 To n
NewX(k) = X(k)
NewY(k) = Y(k)
Next
i = n - 1
'下面對p()數組的n個數（除0以外）進行排列，每產生一種排列方式，坐標數組的數據就對應交換，並計算這一路徑的總距離
Do While i > 0
If p(i) < p(i + 1) Then
For j = n To i + 1 Step -1 '從排列右端開始
If p(i) <= p(j) Then Exit For '找出遞減子序列
Next
temp = p(i): p(i) = p(j): p(j) = temp '將遞減子序列前的數字與序列中比它大的第一個數交換
temp = X(i): X(i) = X(j): X(j) = temp '與之對應的X Y也交換
temp = Y(i): Y(i) = Y(j): Y(j) = temp
For j = n To 1 Step -1 '將這部分排列倒轉
i = i + 1
If i >= j Then Exit For
temp = p(i): p(i) = p(j): p(j) = temp
temp = X(i): X(i) = X(j): X(j) = temp
temp = Y(i): Y(i) = Y(j): Y(j) = temp
Next
m = m + 1
For k = 0 To n - 1
Stance(m) = Stance(m) + Sqr((Y(k + 1) - Y(k)) * (Y(k + 1) - Y(k)) + (X(k + 1) - X(k)) * (X(k + 1) - X(k)))
Next
If Stance(m) <= Smin Then
Smin = Stance(m)
For k = 0 To n
NewX(k) = X(k): NewY(k) = Y(k)
Next
End If
i = n
End If
i = i - 1
Loop
For k = 0 To n
X(k) = NewX(k): Y(k) = NewY(k)
Next '此時的X（） Y（） 就按照最短路徑排列
End Function
『陸』 求出最短路徑，要過程，用Dijkstra演算法。。。
從v1開始遍歷
v2 = 2;
v3 = 5;
v2較小所以跳到v2
v3 = 4;
v4 = 6;
v5 = 8;
v3較小所以跳到v3
v4 = 5;
v6 = 7;
v4較小所以跳到v4
v6 = 6;
v7 = 9;
v6較小所以跳到v6
v7 = 8;
所以最後結果v1 -> v7最短路徑為v1->v2->v3->v4->v6->v7,最短路徑長度為8
『柒』 求！最短路徑演算法 Dijkstra 用C語言編出來
Dijkstra演算法--c++源代碼--by
偉偉豬
[轉貼
2005-12-15
20:21:00
]
發表者:
偉偉豬
/***********************************************
設G=(V,E)是一個每條邊都有非負長度的有向圖，有一個特異的頂點s稱為緣。
單源最短路徑問題，或者稱為最短路徑問題，是要確定從s到V中沒一個其他
頂點的距離，這里從頂點s到x的距離定義為從s到x的最短路徑問題。這個問題
可以用Dijkstra演算法解決。下面我給我了c++下的源代碼！
--by
偉偉豬
************************************************/
#include<iostream.h>
void
main()
{
int
infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input
the
value
of
n:";
cin>>n;
cout<<endl;
d=new
int[n];
s=new
int[n];
p=new
int[n];
w=new
int*[n];
for(i=0;i<n;i++)
{w[i]=new
int[n];}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];
for(s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if(d[i]<infinity)
p[i]=0;
else
p[i]=-1;
}
for(i=1;i<n;i++)
{
t=infinity;k=1;
for(j=1;j<n;j++)
if((!s[j])&&(d[j]<t))
{t=d[j];k=j;}
s[k]=1;//point
k
join
the
S
for
(j=1;j<n;j++)
if((!s[j])&&(d[j]>d[k]+w[k][j]))
{d[j]=d[k]+w[k][j];p[j]=k;}
}
cout<<"從源點到其它頂點的最短距離依次如下：";
for(i=1;i<n;i++)
cout<<d[i]<<"
";
}
/*********
頂點個數用n表示，這里給出的例子n=6
100
1
12
100
100
100
100
100
9
3
100
100
100
100
100
100
5
100
100
100
4
100
13
15
100
100
100
100
100
4
100
100
100
100
100
100
具體例子見
電子工業出版社
《演算法設計技巧與分析》148頁
************/
『捌』 最短路徑演算法 C語言
#include<stdio.h>
#defineMAXNODE108
intpath[MAXNODE+1][MAXNODE+1]={0};
intmain(void)
{
FILE*fpr,*fpw;
intva,vb,i,j,k;
fpr=fopen("in.txt","r");/*讀取的文件名稱in.txt*/
fpw=fopen("out.txt","w");/*path的數據在out.txt中展現*/
while(fscanf(fpr,"%d%d",&va,&vb)!=EOF)
path[va][vb]=path[vb][va]=1;
for(k=1;k<=MAXNODE;++k){
for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(!path[i][k]||!path[k][j])
continue;
if(!path[i][j])
path[i][j]=path[i][k]+path[k][j];
elseif(path[i][j]>path[i][k]+path[k][j])
path[i][j]=path[i][k]+path[k][j];
}
}
}
for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(i==j)
fprintf(fpw,"%-10d",0);
elseif(path[i][j])
fprintf(fpw,"%-10d",path[i][j]);
else
fprintf(fpw,"%-10d",-1);
}
fprintf(fpw," ");
}
return0;
}
注意：floyd演算法中k為最外層，這是動態規劃的思想，不能改變i,j,k的順序！！！
這是之前的答案的錯誤之處。
-1表示不通。
具體程序分析，我可以加你QQ，願意的話，你把QQ寫給我。
『玖』 最短路徑法如何計算
最短路徑演算法有三種，Floyd，dijkstra，Bellman_Ford。其中，Floyd適合用於計算每兩點間的路徑，dijkstra適合稀疏圖，bellman則適合稠密圖中的已知起點終點，計算最短路徑的問題。時間復雜度，floyd演算法為n立方，dijk為n平方，bellman為n平方，其中n是點數。dijk可用堆維護，時間復雜度可減至nlogn，而bellman可用隊列維護，此方法於1994年被國人提出，命名比較土鱉叫SPFA(shortest path faster algorithm。。。)。至於如何計算，有了名字，搜一下就ok。
『拾』 求解：圖論中常見的最短路徑演算法有幾種都是什麼
主要是有三種、、
第一種是最直接的貪心dijkstra演算法、、可以利用堆數據結構進行優化、、缺點就是不能求有負權的最短路與判斷負環、、
第二種是bellman-ford演算法、、根據鬆弛操作的性質是可以來判斷負環的、、時間復雜度是O(nm)的、、
第三種是SPFA演算法、、把他單獨拿出來作為一種演算法並不是非常好的、、他的實質應該是上面的bellman-ford演算法的隊列優化時間復雜度更低、O(KE)、K的值約等於2、、