-
單源最短路徑
鎖定
- 中文名
- 單源最短路徑
- 適用領域
- 算法 圖論 ACM比賽
- 主要方法
- Dijkstra Bellman-Ford SPFA
單源最短路徑Dijkstra算法
單源最短路徑問題描述
給定一個帶權有向圖 G=(V,E) ，其中每條邊的權是一個非負實數。另外，還給定 V 中的一個頂點，稱為源。我們要計算從源到所有其他各頂點的最短路徑長度。這裏的長度是指路上各邊權之和。這個問題通常稱為單源最短路徑問題。
單源最短路徑解決方案
Dijkstra提出按各頂點與源點v間的路徑長度的遞增次序，生成到各頂點的最短路徑的算法。既先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從源點v 到其它各頂點的最短路徑全部求出為止。
單源最短路徑解題思想
將圖G中所有的頂點V分成兩個頂點集合S和T。以v為源點已經確定了最短路徑的終點併入S集合中，S初始時只含頂點v,T則是尚未確定到源點v最短路徑的頂點集合。然後每次從T集合中選擇S集合點中到T路徑最短的那個點，並加入到集合S中，並把這個點從集合T刪除。直到T集合為空為止。
具體步驟
1、選一頂點v為源點，並視從源點v出發的所有邊為到各頂點的最短路徑（確定數據結構：因為求的是最短路徑，所以①就要用一個記錄從源點v到其它各頂點的路徑長度數組dist[],開始時，dist是源點v到頂點i的直接邊長度，即dist中記錄的是鄰接陣的第v行。②設一個用來記錄從源點到其它頂點的路徑數組path[],path中存放路徑上第i個頂點的前驅頂點）。
2、在上述的最短路徑dist[]中選一條最短的，並將其終點（即<v,k>）k加入到集合s中。
3、調整T中各頂點到源點v的最短路徑。 因為當頂點k加入到集合s中後，源點v到T中剩餘的其它頂點j就又增加了經過頂點k到達j的路徑,這條路徑可能要比源點v到j原來的最短的還要短。調整方法是比較dist[k]+g[k,j]與dist[j]，取其中的較小者。
4、再選出一個到源點v路徑長度最小的頂點k,從T中刪去後加入S中，再回去到第三步，如此重複，直到集合S中的包含圖G的所有頂點。
單源最短路徑示例代碼
pascal：
PROCEDURE DIJKSTRA;
VAR
DIST:ARRAY[1..MAXP]OF LONGINT;{距離數組,記錄目前從源點出發已經找到的最短路徑長度}
VISITED:ARRAY[1..MAXP]OF BOOLEAN;{標誌數組,記錄是否已經找到了某一點的最終最短路徑}
I,J,MIN,MINP:LONGINT;
BEGIN
FILLCHAR(VISITED,SIZEOF(VISITED),FALSE);{初始化源點和路徑數組}
FOR I:=1 TO MAXP DO
BEGIN
DIST:=MAP[SOURCE,I];
IF DIST<M THEN
PATH:=SOURCE
ELSE
PATH:=0;
END;{源點的最短路徑肯定是不用找的...}
VISITED[SOURCE]:=TRUE;
{DIJKSTRA的思想是按遞增長度來產生路徑,每次選出當前已經
找到的最短的一條路徑,它必然是一條最終的最短路徑.因此
每次找出當前距離數組中最小的,必然是一條最終的最短路徑}
FOR I:=2 TO MAXP DO
BEGIN
MIN:=INFINITY;
MINP:=0;
FOR J:=1 TO MAXP DO
IF (NOTVISITED[J]) AND (DIST[J]<MIN) THEN
BEGIN
MIN:=DIST[J];
MINP:=J;
END;{已找到源點到點MINP的最短路徑,做上標誌}
VISITED[MINP]:=TRUE;{修改距離數組}
FOR J:=1 TO MAXP DO
IF (NOTVISITED[J]) AND (DIST[MINP]+MAP[MINP,J]<DIST[J]) THEN
BEGIN
DIST[J]:=DIST[MINP]+MAP[MINP,J];
PATH[J]:=MINP;
END;
END;
END;
c++：
//Compute shortest path distances from s,return them in D
void Dijkstra(Graph *G,int *D,int s){ //這裏的s是指計算最小路徑的源，但是題目中沒有用到，應該加一個
//初始化數組D的函數
/*
for(int i =0; i<G->n() ; i++){//僅供參考(本來這個初始化應該在傳入時候就做好的，但是為了符合這個函數)
if(i ==s ) D[i] =0;
else D[i]=INFINITY;
}
*/
int i,v,w;
for(i=0;i<G->n();i++){ //Process the vertices
v=minVertex(G,D);
if(D[v]==INFINITY) return; //Unreachable vertices
G->setMark(v,VISITED);
for(w=G->first(v);w<G->n();w=G->nexr(v,w))
if(D[w]>(D[v]+G->weight(v,w)))
D[w]=D[v]+G->weight(v,w);
}
}
int minVertex(Graph * G, int * D){//找出最小的點
int i , v ;
for(i=0; i<G->n;i++){ //找沒有被訪問的點
if(G->getMark(i)== UNVISITED){
v=i; break;
}
}
for(i++; i<G->n;i++){ //找比上面還小的未被訪問的點（注意此時的i++）
if((G->getMark(i)== UNVISITED)&&D[i]<D[v]))
v=i;
return v;
}
//還有Graph類沒有給出
c：
void dijkstra(int s,WItem dist[],int prev[],Graph G)
{
int i,j;
List L=Listinit();
if(s<1||s>G->n)
Error("Out of bounds");
/*初始化 dist,prev和L*/
for(i=1;1<=G->n;i++)
{
dist[i]=G->a[s][i];
if(dist[i]==G->NoEdge)
prev[i]=0;
else{
prev[i]=s;
ListInsert(0,i,L);
}
}
dist[s]=0;
/*修改dist和prev*/
while
(!ListEmpty(L))
{
/*找L中具有最小dist值的頂點*./
/*將頂點V從表L中刪除，並修改dist的值*/
i=ListDelMin(L,dist);
for(j=1;j<=G->n;j++)
{
if(G->a[i][j]!=G->NoEdge&&(!prev[j]||dist[j]>dist[j]+G->a[i][j]))
{
dist[j]=dist[i]+G->a[i][j];
if(!prev[j])
ListInsert(0,j,L);
prev[]=i;
}
}
}
}
單源最短路徑Bellman-Ford算法
單源最短路徑描述
由於Dijikstra算法對於帶負邊權的圖就無能為力了，但是Bellman-Ford算法就可以解決這個問題。
單源最短路徑解題思想
算法基於動態規劃，反覆用已有的邊來更新最短距離，Bellman-Ford算法的核心思想是鬆弛。如果dist[u]和dist[v]滿足dist[v]>dist[u]+map[u][v],dist[v]就應該被更新為dist[u]+map[u][v]。反覆的利用上式對dist數組進行鬆弛，如果沒有負權迴路的話，應當會在n-1次鬆弛後結束。
單源最短路徑偽代碼
s為源，map[][]記錄圖的信息，map[u][v]為點u到v的邊的長度，結果保存在dist[]；
- 初始化，所有點 i 賦初值dist[i] =+無窮大，出發點為s，dist[s]=0;
- 對於每條邊(u,v)，如果dist[u]!=+無窮大且dist[v]>dist[u]+map[u][v],則dist[v]=dist[u]+map[u][v].
- 循環步驟2n-1次或直到某次中不在更新，進入步驟4.
- 對於每條邊(u,v),如果dist[u]!=+無窮大且dist[v]>dist[u]+map[u][v],則存在負權迴路。
c：
bool bellmanFord(int s,int head[maxn],NODE edge[maxn],int dist[maxn])
{
for(int i =0; i < n; i++) dist[i] = INF;
dist[0] = 0;
for(int i = 0; i < n-1; i++)
{
for(int j = 0; j < n; j++)
{
if(dist[j] == INF) continue;
for(int k = head[j];k != -1; k = edge[k].next)
{
if(edge[k].w != INF&&dist[edge[k].to] > dist[j] + edge[k].w)
dist[edge[k].to] = dist[j] + edge[k].w;
}
}
}
for(int j = 0; j < n; j++)
{
if(dist[j] == INF) continue;
for(k = head[j]; k != -1;k = edge[k].next)
if(edge[k].w != INF&&dist[edge[k].to] > dist[j] + edge[k].w)
return false;
}
return true;
}
單源最短路徑SPFA算法
單源最短路徑描述
SPFA（Shortest Path Faster Algorithm）算法是求單源最短路徑的一種算法，在Bellman-ford算法的基礎上加上一個隊列優化，減少了冗餘的鬆弛操作，是一種高效的最短路算法。在 NOI2018Day1T1歸程 中正式被卡，其時間複雜度為O(nm)，遠劣於Dijkstra的O((n+m)log m)。
單源最短路徑解題思想
我們約定加權有向圖G不存在負權迴路，即最短路徑一定存在。如果某個點進入隊列的次數超過N次則存在負環（SPFA無法處理帶負環的圖）。當然，我們可以在執行該算法前做一次拓撲排序，以判斷是否存在負權迴路，但這不是我們討論的重點。我們用數組d記錄每個結點的最短路徑估計值，而且用鄰接表來存儲圖G。我們採取的方法是動態逼近法：設立一個先進先出的隊列用來保存待優化的結點，優化時每次取出隊首結點u，並且用u點當前的最短路徑估計值對離開u點所指向的結點v進行鬆弛操作，如果v點的最短路徑估計值有所調整，且v點不在當前的隊列中，就將v點放入隊尾。這樣不斷從隊列中取出結點來進行鬆弛操作，直至隊列空為止。定理: 只要最短路徑存在，上述SPFA算法必定能求出最小值。
單源最短路徑偽代碼
SPFA實際上是Bellman-Ford基礎上的隊列優化
SPFA(G,w,s)
1. INITIALIZE-SINGLE-SOURCE(G,s)
2. INITIALIZE-QUEUE(Q)
3. ENQUEUE(Q,s)
4. While Not EMPTY(Q)
5. Do u<-DLQUEUE(Q)
6. For 每條邊(u,v) in E[G]
7. Do tmp<-d[v]
8. Relax(u,v,w)
9. If (d[v] < tmp) and (v不在Q中)
10. ENQUEUE(Q,v)
c++：
bool SPFA(intsource){
deque<int>dq;
int i,j,x,to;
for(i=1;i<=nodesum;i++){
in_sum[i]=0;
in_queue[i]=false;
dist[i]=INF;
path[i]=-1;
}
dq.push_back(source);
in_sum[source]++;
dist[source]=0;
in_queue[source]=true;//初始化完成
while(!dq.empty()){
x=dq.front();
dq.pop_front();
in_queue[x]=false;
for(i=0;i<adjmap[x].size();i++){
to=adjmap[x][i].to;
if((dist[x]<INF)&&(dist[to]>dist[x]+adjmap[x][i].weight)){
dist[to]=dist[x]+adjmap[x][i].weight;
path[to]=x;
if(!in_queue[to]){
in_queue[to]=true;
in_sum[to]++;
if(in_sum[to]==nodesum)
return false;
if(!dq.empty()){
if(dist[to]>dist[dq.front()])
dq.push_back(to);
else dq.push_front(to);
}else
dq.push_back(to);
}
}
}
}
return true;
}
