單源最短路徑

給定一個帶權有向圖G=（V,E），其中每條邊的權是一個實數。另外，還給定V中的一個頂點，稱為源。現在要計算從源到其他所有各頂點的最短路徑長度。這裡的長度就是指路上各邊權之和。這個問題通常稱為單源最短路徑問題。

基本介紹

• 中文名：單源最短路徑
• 適用領域範圍：算法 圖論 ACM比賽
• 主要方法：Dijkstra Bellman-Ford SPFA

Dijkstra算法

問題描述

給定一個帶權有向圖 G=(V,E) ，其中每條邊的權是一個非負實數。另外，還給定 V 中的一個頂點，稱為源。現在我們要計算從源到所有其他各頂點的最短路徑長度。這裡的長度是指路上各邊權之和。這個問題通常稱為單源最短路徑問題。

Dijkstra算法的解決方案

Dijkstra提出按各頂點與源點v間的路徑長度的遞增次序，生成到各頂點的最短路徑的算法。既先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從源點v 到其它各頂點的最短路徑全部求出為止。

Dijkstra算法的解題思想

將圖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;VARDIST:ARRAY[1..MAXP]OF LONGINT;{距離數組,記錄目前從源點出發已經找到的最短路徑長度}VISITED:ARRAY[1..MAXP]OF BOOLEAN;{標誌數組,記錄是否已經找到了某一點的最終最短路徑}I,J,MIN,MINP:LONGINT;BEGINFILLCHAR(VISITED,SIZEOF(VISITED),FALSE);{初始化源點和路徑數組}FOR I:=1 TO MAXP DOBEGINDIST:=MAP[SOURCE,I];IF DIST<M THENPATH:=SOURCEELSEPATH:=0;END;{源點的最短路徑肯定是不用找的...}VISITED[SOURCE]:=TRUE;{DIJKSTRA的思想是按遞增長度來產生路徑,每次選出當前已經找到的最短的一條路徑,它必然是一條最終的最短路徑.因此每次找出當前距離數組中最小的,必然是一條最終的最短路徑}FOR I:=2 TO MAXP DOBEGINMIN:=INFINITY;MINP:=0;FOR J:=1 TO MAXP DOIF (NOTVISITED[J]) AND (DIST[J]<MIN) THENBEGINMIN:=DIST[J];MINP:=J;END;{已找到源點到點MINP的最短路徑,做上標誌}VISITED[MINP]:=TRUE;{修改距離數組}FOR J:=1 TO MAXP DOIF (NOTVISITED[J]) AND (DIST[MINP]+MAP[MINP,J]<DIST[J]) THENBEGINDIST[J]:=DIST[MINP]+MAP[MINP,J];PATH[J]:=MINP;END;END;END;

c++：

//Compute shortest path distances from s,return them in Dvoid 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 verticesv=minVertex(G,D);if(D[v]==INFINITY) return; //Unreachable verticesG->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的解題思想

算法基於動態規劃，反覆用已有的邊來更新最短距離，Bellman-Ford算法的核心思想是鬆弛。如果dist[u]和dist[v]滿足dist[v]>dist[u]+map[u][v],dist[v]就應該被更新為dist[u]+map[u][v]。反覆的利用上式對dist數組進行鬆弛，如果沒有負權迴路的話，應當會在n-1次鬆弛後結束。

Bellman-Ford算法的偽代碼

s為源，map[][]記錄圖的信息，map[u][v]為點u到v的邊的長度，結果保存在dist[]；

1. 初始化，所有點 i 賦初值dist[i] =+無窮大，出發點為s，dist[s]=0;
   
2. 對於每條邊(u,v)，如果dist[u]!=+無窮大且dist[v]>dist[u]+map[u][v],則dist[v]=dist[u]+map[u][v].
   
3. 循環步驟2n-1次或直到某次中不在更新，進入步驟4.
   
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)。

SPFA算法的解題思想

我們約定加權有向圖G不存在負權迴路，即最短路徑一定存在。如果某個點進入佇列的次數超過N次則存在負環（SPFA無法處理帶負環的圖）。當然，我們可以在執行該算法前做一次拓撲排序，以判斷是否存在負權迴路，但這不是我們討論的重點。我們用數組d記錄每個結點的最短路徑估計值，而且用鄰接表來存儲圖G。我們採取的方法是動態逼近法：設立一個先進先出的佇列用來保存待最佳化的結點，最佳化時每次取出隊首結點u，並且用u點當前的最短路徑估計值對離開u點所指向的結點v進行鬆弛操作，如果v點的最短路徑估計值有所調整，且v點不在當前的佇列中，就將v點放入隊尾。這樣不斷從佇列中取出結點來進行鬆弛操作，直至佇列空為止。定理: 只要最短路徑存在，上述SPFA算法必定能求出最小值。

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++：

boolSPFA(intsource)

{

deque<int>dq;

inti,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);

}

}

}

}

returntrue;

}