路徑最短演算法
㈠ k最短路徑演算法能作為論文中的一個演算法嘛
現在，我們准備介紹計算機科學史上偉大的成就之一：Dijkstra最短路徑演算法[1]。這個演算法適用於邊的長度均不為負數的有向圖，它計算從一個起始頂點到其他所有頂點的最短路徑的長度。在正式定義這個問題（3.1節）之後，我們講解這個演算法（3.2節）以及它的正確性證明（3.3節），然後介紹一個簡單直接的實現（3.4節）。在第4章中，我們將看到這種演算法的一種令人驚嘆的快速實現，它充分利用了堆這種數據結構。
3.1單源最短路徑問題
3.1.1問題定義
Dijkstra演算法解決了單源最短路徑問題。[2]
問題：單源最短路徑
輸入：有向圖G=(V, E)，起始頂點s∈V，並且每條邊e∈E的長度e均為非負值。
輸出：每個頂點v∈V的dist(s,v)。
注意，dist(s,v)這種記法表示從s到v的最短路徑的長度（如果不存在從s到v的路徑，dist(s,v)就是+∞）。所謂路徑的長度，就是組成這條路徑的各條邊的長度之和。例如，在一個每條邊的長度均為1的圖中，路徑的長度就是它所包含的邊的數量。從頂點v到頂點w的最短路徑就是所有從v到w的路徑中長度最短的。
例如，如果一個圖表示道路網，每條邊的長度表示從一端到另一端的預期行車時間，那麼單源最短路徑問題就成為計算從一個起始頂點到所有可能的目的地的行車時間的問題。
小測驗3.1
考慮單源最短路徑問題的下面這個輸入，起始頂點為s，每個邊都有一個標簽標識了它的長度：
從s出發到s、v、w和t的最短距離分別是多少？
（a）0，1，2，3
（b）0，1，3，6
（c）0，1，4，6
（d）0，1，4，7
（正確答案和詳細解釋參見3.1.4節。）
3.1.2一些前提條件
方便起見，我們假設本章中的輸入圖是有向圖。經過一些微小的戲劇性修改之後，Dijkstra演算法同樣適用於無向圖（可以進行驗證）。
另一個前提條件比較重要。問題陳述已經清楚地表明：我們假設每條邊的長度是非負的。在許多應用中（例如計算行車路線），邊的長度天然就是非負的（除非涉及時光機器），完全不需要擔心這個問題。但是，我們要記住，圖的路徑也可以表示抽象的決策序列。例如，也許我們希望計算涉及購買和銷售的金融交易序列的利潤。這個問題相當於在一個邊的長度可能為正也可能為負的圖中尋找最短路徑。在邊的長度可能為負的應用中，我們不應該使用Dijkstra演算法，具體原因可以參考3.3.1節。[3]
3.1.3為什麼不使用寬度優先的搜索
如2.2節所述，寬度優先的搜索的一個「殺手」級應用就是計算從一個起始頂點出發的最短路徑。我們為什麼需要另一種最短路徑演算法呢？
記住，寬度優先的搜索計算的是從起始頂點到每個其他頂點的邊數最少的路徑，這是單源最短路徑問題中每條邊的長度均為1這種特殊情況。我們在小測驗3.1中看到，對於通用的非負長度邊，最短路徑並不一定是邊數最少的路徑。最短路徑的許多應用，例如計算行車路線或金融交易序列，不可避免地涉及不同長度的邊。
但是，讀者可能會覺得，通用的最短路徑問題與這種特殊情況真的存在這么大的區別嗎？如圖3.1所示，我們不能把一條更長的邊看成3條長度為1的邊組成的路徑嗎？
圖3.1路徑
事實上，「一條長度為正整數
的邊」和「一條由
條長度為1的邊所組成的路徑」之間並沒有本質的區別。在原則上，我們可以把每條邊展開為由多條長度為1的邊組成的路徑，然後應用寬度優先的搜索對圖進行展開來解決單源最短路徑問題。
這是把一個問題簡化為另一個問題的一個例子。在這個例子中，就是從邊的長度為正整數的單源最短路徑問題簡化為每條邊的長度均為1的特殊情況。
這種簡化所存在的主要問題是它擴大了圖的規模。如果所有邊的長度都是小整數，那麼這種擴張並不是嚴重的問題。但在實際應用中，情況並不一定如此。某條邊的長度很可能比原圖中頂點和邊的總數還要大很多！寬度優先的搜索在擴張後的圖中的運行效率是線性時間，但這種線性時間並不一定接近原圖長度的線性時間。
Dijkstra演算法可以看成是在擴張後的圖上執行寬度優先的搜索的一種靈活模擬，它只對原始輸入圖進行操作，其運行時間為近似線性。
關於簡化
如果一種能夠解決問題B的演算法可以方便地經過轉換解決問題A，那麼問題A就可以簡化為問題B。例如，計算數組的中位元素的問題可以簡化為對數組進行排序的問題。簡化是演算法及其限制的研究中非常重要的概念，具有極強的實用性。
我們總是應該尋求問題的簡化。當我們遇到一個似乎是新的問題時，總是要問自己：這個問題是不是一個我們已經知道怎樣解決的問題的偽裝版本呢？或者，我們是不是可以把這個問題的通用版本簡化為一種特殊情況呢？
3.1.4小測驗3.1的答案
正確答案：（b）。從s到本身的最短路徑的長度為0以及從s到v的最短路徑的長度為1不需要討論。頂點w稍微有趣一點。從s到w的其中一條路徑是有向邊(s,w)，它的長度是4。但是，通過更多的邊可以減少總長度：路徑s→v→w的長度只有1+2=3，它是最短的s−w路徑。類似地，從s到t的每條經過兩次跳躍的路徑的長度為7，而那條更迂迴的路徑的長度只有1+2+3=6。
3.2Dijkstra演算法
3.2.1偽碼
Dijkstra演算法的高層結構與第2章的圖搜索演算法相似。[4]它的主循環的每次迭代處理一個新的頂點。這個演算法的高級之處在於它採用了一種非常「聰明」的規則選擇接下來處理哪個頂點：就是尚未處理的頂點中看上去最靠近起始頂點的那一個。下面的優雅偽碼精確地描述了這個思路。
㈡ 最短路徑演算法如何選取最短的和第二短的
隨便用一種最短路徑演算法 然後更新時先更新最短路再用最短路更新次短路
㈢ 記錄所有最短路徑的最短路徑演算法
沒有一個演算法是萬能的
Dijkstra:單源最短路徑
Floyd:每對點最短路徑
SPFA(Bellmanford+隊列):快速單源最短路徑(可負權)
還有很多求最短路徑的演算法，但是歸其根本，無外乎：
Label Setting和Label Correcting兩大類，其實就是搜索法+動態規劃。
只要靈活地掌握了搜索法、動態規劃和圖論，這些演算法就都會了。
㈣ 最短路徑演算法作用
可以實現距離最短以及時間最短，從而為你節約行程的成本
㈤ 最短路徑演算法 Dijkstra 用C語言編出來
#include"iostream.h"
#include"stdlib.h"
#define MAXPOINT 3//定義最大的頂點數目
#define limit 32767 //設置沒有路徑的權代替無窮大
struct record{ //沒個頂點的數據結構設置為一個數組隊列
int number; //頂點號
int flag; //標志是否從隊列中被選過如果為1表示選過為0表示未選
int allpath; //從源點到這個點的當前最短距離（權最小）
}path[MAXPOINT+1];
int cost[MAXPOINT+1][MAXPOINT+1]; //用來表示圖的鄰接矩陣
void main()
{int i,j,temp,front=1,rear=MAXPOINT,N,minnumber;
//temp表示在數組隊列中的當前下標 front表示隊列首 rear表示隊列尾
//N 表示待輸入的源點號碼 minnumber 表示選中的點的號碼
int min=32768; //設置一個初始值
for(i=1;i<=MAXPOINT;i++)
for(j=1;j<=MAXPOINT;j++)
{cout<<"請輸入從第"<<i<<"點到第"<<j<<"點的路徑長度(權)如果沒有路徑的話請輸入'32767' "<<endl;
cin>>cost[i][j]; //初始化所有點之間的（權）路徑值
}
//cout<<"請輸入源點號"<<endl; //輸入一個起點
//cin>>N;
for(N=MAXPOINT;N>=1;N--)//把每一個點輪流地都設置為起點，可以求出任意一對頂點之間的最短路徑
{ for(i=front;i<=rear;i++) //初始化每個點的信息
{if(i==N)
path[i].allpath=0;
else
path[i].allpath=limit;
path[i].flag=0;
path[i].number=i;
}
while(rear>=1) //控制循環次數
{for(temp=front;temp<=MAXPOINT;temp++)
{ if(path[temp].allpath<min&&path[temp].flag==0)//選出一個具有最值
//的點
{ minnumber=path[temp].number;
min=path[temp].allpath ;
}
}
min=32768;
path[minnumber].flag=1;//把選中的點的標志變數置1表示已經被選過避免選中
for(i=1;i<=MAXPOINT;i++)//進行類似廣度優先搜索，更新最短路徑
{if((i!=minnumber)&&(path[minnumber].allpath+cost[minnumber][i]<path[i].allpath))
path[i].allpath=path[minnumber].allpath+cost[minnumber][i];
}
rear--;//次數減1
}
rear=MAXPOINT; //恢復數組以便於下一點的循環
for(j=1;j<=MAXPOINT;j++)
{ cout<<"第"<<N<<"點到第"<<j<<"點的最短路徑長度（權）為";
cout<<path[j].allpath <<endl;
}
}
}
//這個程序可以求出任意一對頂點之間的最短路徑，不過這種演算法效率還不是很高，還有其他演算法待續
㈥ 求解：圖論中常見的最短路徑演算法有幾種都是什麼
主要是有三種、、
第一種是最直接的貪心dijkstra演算法、、可以利用堆數據結構進行優化、、缺點就是不能求有負權的最短路與判斷負環、、
第二種是bellman-ford演算法、、根據鬆弛操作的性質是可以來判斷負環的、、時間復雜度是O(nm)的、、
第三種是SPFA演算法、、把他單獨拿出來作為一種演算法並不是非常好的、、他的實質應該是上面的bellman-ford演算法的隊列優化時間復雜度更低、O(KE)、K的值約等於2、、
㈦ 求出最短路徑，要過程，用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
㈧ 求一個最短路徑的演算法
以前看到過，貼給你
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