- 中文名
- 单源最短路径
- 适用领域
- 算法 图论 ACM比赛
- 主要方法
- Dijkstra Bellman-Ford SPFA
给定一个带权有向图 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的所有顶点。
pasc牛雄境祖良al：
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算法的核心思想是松弛。如果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[ ]；
- 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（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;
}
