最短路问题(short-path problem)若网络中的每条边都有一个权值值(长度、成本、时间等)，则找出两节点(通常是源节点与结束点)之间总权和最小的路径就是最短路问题。

最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。

最短路问题，我们通常归属为三类：单源最短路径问题（确定起点或确定终点的最短路径问题）、确定起点终点的最短路径问题（两节点之间的最短路径）1、Dijkstra算法：用邻接矩阵a表示带权有向图，d为从v0出发到图上其余各顶点可能达到的最短路径长度值，以v0为起点做一次dijkstra，便可以求出从结点v0到其他结点的最短路径长度代码：procedure dijkstra（v0：longint）；//v0为起点做一次dijkstrabegin//a数组是邻接矩阵，a[i,j]表示i到j的距离，无边就为maxlongintfor i:=1 to n do d[i]:=a[v0,i];//初始化d数组（用于记录从v0到结点i的最短路径）， fillchar(visit,sizeof(visit),false);//每个结点都未被连接到路径里visit[v0]:=true;//已经连接v0结点for i:=1 to n-1 do//剩下n-1个节点未加入路径里；beginmin:=maxlongint;//初始化minfor j:=1 to n do//找从v0开始到目前为止，哪个结点作为下一个连接起点（*可优化） if (not visit[j]) and (min>d[j]) then//结点k要未被连接进去且最小begin min:=d[j];k:=j;end;visit[k]:=true;//连接进去for j:=1 to n do//刷新数组d，通过k来更新到达未连接进去的节点最小值，if (not visit[j]) and (d[j]>d[k]+a[k,j]) then d[j]:=a[k,j]+d[k];end;writeln(d[n]);//结点v0到结点n的最短路。

思考：在实现步骤时，效率较低需要O(n)，使总复杂度达到O(n^2)。

对此可以考虑用堆这种数据结构进行优化，使此步骤复杂度降为O(log(n))(总复杂度降为O(n log(n))。

实现：1. 将与源点相连的点加入堆（小根堆），并调整堆。

2. 选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。

3. 处理与u相邻（即下一个）未被访问过的，满足三角不等式的顶点1):若该点在堆里，更新距离，并调整该元素在堆中的位置。

2):若该点不在堆里，加入堆，更新堆。

4. 若取到的u为终点，结束算法；否则重复步骤2、3。

**优化代码：(DIJKSTRA+HEAP)program SSSP;{single source shortest path}{假设一个图的最大节点数为1000，所有运算在integer范围内}{程序目标：给定有向图的邻接表，求出节点1到节点n的最短路径长度}const maxn=1000;{最大节点数}varn:integer;{节点个数}list:array[1..maxn,1..maxn] of integer;{邻接矩阵，表示边的长度}count:integer;{堆内元素个数计数器}heap:array[1..maxn] of integer;{heap[i]表示堆内的第i的元素的节点编号} pos:array[1..maxn] of integer;{表示编号为i的元素在堆内的位置}key:array[1..maxn] of integer;{表示节点1到节点i的最短距离}exist:array[1..maxn] of boolean;{表示节点i是否存在于堆中}i,j,now:integer;procedure swap(var i,j:integer);{交换整数i和j}//省略procedure heapify(p:integer);{向下调整堆的过程}var best:integer;beginbest:=p;//下面两个if是分别判断根和左、右孩子最短距离的大小if (p*2<=count) and (key[heap[p*2]]<key[heap[best]]) then best:=p*2;if (p*2+1<=count) and (key[heap[p*2+1]]<key[heap[best]]) then best:=p*2+1; if best<>p then//若根有所变动，即跟比左右孩子都大（最短距离）beginswap(pos[heap[p]],pos[heap[best]]);//互换节点heap[p]、heap[best]在堆的位置swap(heap[p],heap[best]);//互换堆中元素p、bestheapify(best);//继续调整互换后的元素bestend;end;procedure modify(id,new_key:integer);{判断new_key与key[id]大小，并修改key[id]大小}var p:integer;beginif (new_key<key[id]) thenbegin//修改key[id]:=new_key;//更新最短距离p:=pos[id];//结点id在堆中的位置while (p>1) and (key[heap[p]]<key[heap[p div 2]｛父｝]) do//向上调整beginswap(pos[heap[p]],pos[heap[p div 2]]);swap(heap[p],heap[p div 2]);p:=p div 2;//更上一层end;end;end;procedure extract（抽出）(var id,dis:integer);{读取堆中最小元素的节点编号和节点1到该节点的距离}beginid:=heap[1];//堆顶dis:=key[id];dec(count);//出堆if (count>0) then//堆里还有元素beginswap(pos[heap[1]],pos[heap[count+1]]);// 堆顶的元素和第count+1个元素换位置swap(heap[1],heap[count+1]);//把堆顶的元素扔到count后面去，heapify(1);//此时堆顶不一定是最小的~扔到下面去，把最小的搞上来。

end;end;beginreadln(n);init；//读入邻接矩阵，没有连线的为maxint；省略for i:=1 to n do{初始化}beginexist[i]:=true;//所有元素入堆pos[i]:=i; heap[i]:=i; key[i]:=maxint;end;count:=n; key[1]:=0;{dijkstra算法的主要操作}while (count>0) dobeginextract(i,now); exist[i]:=false;if now=maxint then break;//无路可走了，overfor j:=1 to n doif (exist[j]) then modify(j,now+list[i,j]);end;{输出}if key[n]=maxint then writeln('Not Connected!'){节点1和节点n不连通}else writeln(key[n]);{连通}end.SPFA+(前向星、循环队列、邻接表、链表）2、SPFA算法（Shortest Path Faster Algorithm）：spfa算法是西南交通大学段凡丁于1994年发表的.简介：给定的图存在负权边时，dijkstra等便无用武之地，spfa算法便派上用场了。

若有向加权图G不存在负权回路，即最短路径一定存在，用数组d记录每个结点的最短路径估计值，用邻接表来存储图G。

采取方法是动态逼近法：设立一个队列用来保存待优化的结点，优化时每次取出队首结点u，且用到达u点当前的最短路径估计值d[u]对点u所指向的结点v进行松弛操作，若v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾（已在队列里就不用放到队尾）。

这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

若某点入队的次数超过n次，则存在负环，spfa无法处理这样的图。

定理: 只要最短路径存在，spfa算法必定能求出最小值。

证明：松弛操作原理：“三角形两边之和大于第三边”，在信息学中称三角不等式。

每次将点放入队尾，都是经松弛操作达到的。

所谓对i,j进行松弛，即if (d[j]>d[i]+w[i,j]）then d[j]:=d[i]+w[i,j]，每次优化都可能将某个点v的最短路径估计值d[v]变小，d数组将会越来越小。

由于图中不存在负权回路，所以每个结点都有最短路径值，算法不会无限执行下去，随着d值的逐渐变小，到最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。

时间复杂度：O(ke)， k为所有顶点进队的平均次数，可以证明k一般小于等于2。

* 实现方法：建立一个队列，初始时队列里只有起始点，用d数组记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。

然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。

重复执行直到队列为空求路径方案：若这幅图是地图的模型，除了算出最短路径长度，还要知道路径方案。

设path数组，path[i]表示从起点到i的最短路径中，结点i之前一个结点的编号，我们只需在结点u对结点v进行松弛时，标记下path[v]=u即可。

spfa算法采用邻接表来存储图，方法是动态优化逼近法。

算法中用队列queue用来保存待优化的结点，优化时从队首取出一个点w，并且用w点的当前路径d[w]去调整相连各点的路径值d[j]，若有调整，即d[j]的值改小，就将j点放入queue队列以待进一步优化。

重复执行，直至队空。

此时d数组便保存了从起点到各点的最短路径值。

实例：设有向图g={v，e}，e={<v0,v1>,<v0,v4>,<v1,v2>,<v1,v4>,<v2,v3>,<v3,v4>,<v4,v2>}={2,10,3,7,4,5,6}，v={v0,v1,v2,v3,v4}，见上图：算法执行时各步的queue队的值和d数组的值由下表所示。