最短路径是图论中一个很经典的问题：给定图G(V,E)，求一条从起点到终点的路径，使得这条路径上经过的所有边的边权之和最小。
对任意给出的图G(V,E)和起点S、终点T，如何求从S到T的最短路径。解决最短路径问题的常用算法有Dijkstra算法、Bellman-Ford算法、SPEA算法和Floyd算法。
1.Dijkstra算法
Dijkstra算法(读者可以将其读作“迪杰斯特拉算法”)用来解决单源最短路问题，即给定图G和起点s，通过算法得到S到达其他每个顶点的最短距离。Dijkstra的基本思想是对图G(V,B)设置集合S，存放已被访问的顶点，然后每次从集合V-S中选择与起点s的最短距离最小的一个顶点(记为u)，访问并加入集合S。之后，令顶点u为中介点，优化起点s与所有从u能到达的顶点v之间的最短距离。这样的操作执行n次(n为顶点个数)，直到集合S已包含所有顶点。
单源最短路径：从起点V出发，每个顶点之间的路程尽可能短，即从起点到达其他所有顶点都必须是最短距离。
①将地图上所有边都抹去，只有当到达这个顶点后才把从这个顶点出去的边显现(笔者插话：这个操作在实际编写代码时是自然成立、不需要人为控制的，但是在这单独提出来对理解Dijkstra操作的过程很有帮助)。
②在地图中的顶点V(0≤i≤5)上记录从起点V0到达该城市所需要的最短距离。由于在①中所有边都被抹去了，因此在初始状态下除了V0到达V0的距离是0之外，从V到达其他顶点的距离都是无穷大(记为INF)。为了方便叙述，在下文中某几处出现的最短距离都是指从起点V0到达顶点V的最短距离。
下面是行动策略：
①由于要攻占六个顶点，因此将步骤②③执行六次，每次攻占一个顶点(如果是n个顶点，那么就执行n次)。
②每次都从还未攻占的城市中选择当前距离起点V0最近的城市(即地图的顶点上记录的最短距离最小的未到达的顶点，记为Vk(0≤k≤5)。
③到达顶点Vk后，开放地图上从Vk出发的所有边，并査看以Vk为中介点的情况下，能否使从起点V0到达某些还未到达的顶点的最短距离变小。如果能，则将那个最短距离覆盖到对应的城市上(因为开放了从Vk出发的边，因此有了改善某些顶点最短距离的可能，且当前只有Vk能够优化这个最短距离)。
首先，Dijkstra算法解决的是单源最短路问题，即给定图G(V,E)和起点s(起点又称为源点)，求从起点s到达其它顶点的最短距离。Dijkstra算法的策略是：设置集合S存放已被访问的顶点(即已到达的顶点)，然后执行n次下面的两个步骤(n为顶点个数)。
①每次从集合V-S(即未到达的顶点)中选择与起点s的最短距离最小的一个顶点(记为u)，访问并加入集合S(即令其已被访问)。
②之后，令顶点u为中介点，优化起点s与所有从u能到达的顶点v之间的最短距离。
Dijkstra算法的具体实现：由于Dijkstra算法的策略比较偏重于理论化，因此为了方便编写代码，需要想办法来实现策略中两个较为关键的东西，即集合S的实现、起点s到达顶点Vi(0≤i≤n-1)的最短距离的实现。
①集合S可以用一个bool型数组vis[]来实现，即当vis[i]=true时表示顶点Vi已被访问，当vis[i]=false时表示顶点Vi未被访问。
②令int型数组表示起点s到达顶点V的最短距离，初始时除了起点s的的d[s]赋为0，其余顶点都赋为一个很大的数(10^9)来表示INF，即不可达。
接下来看看实现Dijkstra算法的伪代码。其实很短，不难，希望读者能够结合上面好好理解一下这个伪代码，然后再往下看：
//G为图，一般设成全局变量;数组d为源点到达各点的最短路径长度，s为起点
Dijkstra(G,d[],s){
初始化
for(循环n次){
u = 使d[u]最小的还未访问的顶点的标号;
记u已被访问;
for(从u出发能到达的所有顶点v){
if(v未被访问&&以u为中介点使s到顶点v的最短距离d[v]更优){
优化d[v];
}
}
}
}
由于图可以使用邻接矩阵或者邻接表来实现，因此也就会有两种写法，但是这两种写法都是以上面的伪代码为基础的，区别主要集中在枚举从u出发能到达的顶点v上面：邻接矩阵需要枚举所有顶点来查看v是否可由u到达;邻接表则可以直接得到u能到达的顶点v。在写出具体函数之前，需要先定义MAXV为最大顶点数、INF为一个很大的数字：
const int MAXV = 1000; //最大顶点数
const int INF = 1000000000; //设INF为一个很大的数
下面来看邻接矩阵和邻接表对Dijkstra算法的具体实现代码。
(1)邻接矩阵版
适用于点数不大(例如V不超过1000)的情况，相对好写。代码如下：
int n,G[MAXV][MAXV]; //n为顶点数，MAXV为最大顶点数
int d[maxv]; //起点到达各点的最短路径长度
bool vis[MAXV] = {false}; //标记数组，vis[i]==true表示已访问。初始值均为false
void Dijkstra(int s){ //s为起点
fill(d,d+MAXV,INF); //fill函数将整个d数组赋值为INF(慎用memset)
d[s] = 0; //起点s到达自身的距离为0
for(int i=0;i
int u=-1,MIN=INF; //u使d[u]最小，MIN存放最小的d[u]
for(int j=0;j
if(vis[j]==false && d[j]
u=j;
MIN=d[j];
}
}
//找不到小于INF的d[u]，说明剩下的顶点和起点s不连通
if(u==-1)
return;
vis[u] = true; //标记u为已访问
for(int v=0;v
//如果v未能访问&&u能到达v&&以u未终结点可以使d[v]更优
if(vis[v]==false && G[u][v] != INF && d[u]+G[u][v] < d[v]){ d[v] = d[u]+G[u][v]; //优化d[v] } } } } 从复杂度来看，主要是外层循环O(V)(V就是顶点个数n)与内层循环(寻找最小的d[u]需要O(V)、枚举v需要O(V))产生的，总复杂度为O(V*(V+V))=O(V^2)。 (2)邻接表版 vector Adj[MAXV]; //图 G，Adj[u]存放从顶点u出发可以到达的所有顶点 int n; // n为顶点数，图G使用邻接表实现，MAXV为最大顶点数 int d[maxv]; //起点到达各点的最短路径长度 bool vis[MAXV] = {false}; //标记数组，vis[i]==true表示已访问。初始值均为false void Dijkstra(int s){ //s为起点 fill(d,d+MAXV,INF); //fill函数将整个d数组赋值为INF(慎用memset) d[s] = 0; //起点s到达自身的距离为0 for(int i=0;i int u=-1,MIN=INF; //u使d[u]最小，MIN存放最小的d[u] for(int j=0;j if(vis[j]==false && d[j] u=j; MIN=d[j]; } } //找不到小于INF的d[u]，说明剩下的顶点和起点s不连通 if(u==-1) return; vis[u] = true; //标记u为已访问 for(int j=0;j int v = Adj[u][j].v; //通过邻接表直接获得u能到达的顶点v if(vis[v]==false && d[u]+G[u][j].dis < d[v]){ //如果v未能访问&&以u未终结点可以使d[v]更优 d[v] = d[u]+G[u][v]; //优化d[v] } } } } 从复杂度来看，主要是外层循环O(V)与内层循环(寻找最小的d[u]需要O(V)、枚举V需要O(adj[u].size))产生的。又由于对整个程序来说，枚举v的次数总共为O(E)，因此总复杂度为O(V^2+E)。 可以注意到，上面的做法都是复杂度O(V)级别的，其中由于必须把每个顶点都标记为已访问，因此外层循环的O(V)时间是无法避免的，但是寻找最小d[u]的过程却可以不必达到O(V)的复杂度，而可以使用堆优化来降低复杂度。最简洁的写法是直接使用STL中的优先队列priority_ queue，这样使用邻接表实现的Dijkstra算法的时间复杂度可以降为O(VlogV+E)。此外，Dijkstra算法只能应对所有边权都是非负数的情况，如果边权出现负数，那么 Dijkstra算法很可能会出错，这时最好使用SPFA算法。 下面以上面的例图为例编写代码，并最终输出从起点V0到达所有顶点(包括V0)的最短距离，程序代码如下： #include< cstdio>
#include< algorithm>
using namespace std;
const int MAXV = 1000; //最大顶点数
const int INF = 1000000000; //设INF为一个很大的数
int n,m,s,G[MAXV][MAXV]; //n为顶点数，m为边数，s为起点
int d[MAXV]; //起点到达各点的最短路径长度
bool vis[MAXV] = {false}; //标记数组，vis[i]==true表示已访问。初始值均为false
void Dijkstra(int s){ //s为起点
fill(d,d+MAXV,INF); //fill函数将整个d数组赋值为INF(慎用memset)
d[s] = 0; //起点s到达自身的距离为0
for(int i=0;i
int u=-1,MIN=INF; //u使d[u]最小，MIN存放最小的d[u]
for(int j=0;j
if(vis[j]==false && d[j]
u=j;
MIN=d[j];
}
}
//找不到小于INF的d[u]，说明剩下的顶点和起点s不连通
if(u==-1)
return;
vis[u] = true; //标记u为已访问
for(int v=0;v
//如果v未能访问&&u能到达v&&以u未终结点可以使d[v]更优
if(vis[v]==false && G[u][v] != INF && d[u]+G[u][v] < d[v]){ d[v] = d[u]+G[u][v]; //优化d[v] } } } } int main(){ int u,v,w; scanf("%d%d%d",&n,&m,&s); //顶点个数，边数，起点编号 fill(G[0],G[0]+MAXV*MAXV,INF); //初始化图G for(int i=0;i scanf("%d%d%d",&u,&v,&w); //输入u,v以及u->v的边权
G[u][v] = w;
}
Dijkstra(s); // Dijkstra算法入口
for(int i=0;i
printf("%d ",d[i]); //输出所有顶点的最短距离
}
return 0;
}
输入数据：
6 8 0
0 1 1
0 3 4
0 4 4
1 3 2
2 5 1
3 2 2
3 4 3
4 5 3
输出结果：
0 1 5 3 4 6
有的读者会有疑问，如果题目给出的是无向边(即双同边)而不是有向边，又该如解决呢?这其实很容易，只需要把无向边当成两条指向相反的有向边即可。对邻接矩阵来说，一条u与v之间的无向边在输入时可以分别对G[u][v]和G[v][u]赋以相同的边权;而对邻接表来说，只需要在u的邻接表Adj[u]末尾添加上v，并在v的邻接表Adj[v]末尾添加上u即可。
之前一直在讲最短距离的求解，但是还没有讲到最短路径本身怎么求解。那么接下来学习一下最短路径的求法。在Dijkstra算法的伪代码部分，有这么一段：
if(v未被访问&&以u为中介点使s到顶点v的最短距离d[v]更优){
优化d[v];
}
这个地方提到的条件“以u为中介点可以使起点s到顶点v的最短距离d[v]更优”隐含了这样一层意思：使d[v]变得更小的方案是让u作为从s到v最短路径上v的前一个结点(即s→…→u→v)。这就给我们一个启发：不妨把这个信息记录下来。于是可以设置数组pre[]令pre[v]表示从起点s到顶点v的最短路径上v的前一个顶点(即前驱结点)的编号。这样当伪代码中的条件成立时，就可以将u赋给pre[v]，最终就能把最短路径上每一个顶点的前驱结点记录下来。而在伪代码部分只需要在if内增加一行：
if(v未被访问&&以u为中介点使s到顶点v的最短距离d[v]更优){
优化d[v];
令v的前驱为u;
}
具体实现中，以邻接矩阵为例：
int n,G[MAXV][MAXV]; //n为顶点数，MAXV为最大顶点数
int d[maxv]; //起点到达各点的最短路径长度
int pre[MAXV]; //pre[v]表示从起点到顶点v的最短路径v的前一个顶点
bool vis[MAXV] = {false}; //标记数组，vis[i]==true表示已访问。初始值均为false
void Dijkstra(int s){ //s为起点
fill(d,d+MAXV,INF); //fill函数将整个d数组赋值为INF(慎用memset)
for(int i=0;i
pre[i] = i; //初始状态设每一个点的前驱为自身
d[s] = 0; //起点s到达自身的距离为0
for(int i=0;i
int u=-1,MIN=INF; //u使d[u]最小，MIN存放最小的d[u]
for(int j=0;j
if(vis[j]==false && d[j]
u=j;
MIN=d[j];
}
}
//找不到小于INF的d[u]，说明剩下的顶点和起点s不连通
if(u==-1)
return;
vis[u] = true; //标记u为已访问
for(int v=0;v
//如果v未能访问&&u能到达v&&以u未终结点可以使d[v]更优
if(vis[v]==false && G[u][v] != INF && d[u]+G[u][v] < d[v]){ d[v] = d[u]+G[u][v]; //优化d[v] pre[v] = u; //记录v的前驱顶点是u } } } } 新增的只有3、8~9、27行。 到这一步，只是求出了最短路径上每个点的前驱，那么如何求整条路径呢?以下图这个很简单的路径来说明。从算法中已经可以得到了每个顶点的前驱： pre[4] = 3; pre[3] = 2; pre[2] = 1; pre[3] = 1; 那么，当想要知道从起点V1到达V4的最短路径，就需要先从pre[4]得到V4的前驱顶点是V3，然后从pre[3]得到V3的前驱顶点是V2，再从pre[2]得到V2的前驱顶点是V1。 这听起来有点像递归?没错，就是用递归不断利用pre[]的信息寻找前驱，直至到达起点V1后从递归深处开始输出。 这个递归写起来很简洁，读者可以好好体会一下： void DFS(int s, int v){ //s为起点编号，v为当前访问的顶点编号(从终点开始递归) if(v ==s){ //如果当前以及到达起点s，则输出起点并返回 printf("%d\n",s); return; } DFS(s,pre[v]); //递归访问v的前驱顶点pre[v] printf("%d\n",v); //从最深处return回来之后，输出每一层的顶点号 } 至此，Dijkstra算法的基本用法大家都应该已经掌握。但是题目肯定不会考得这么“裸”，更多时候会出现这样一种情况，即从起点到终点的最短距离最小的路径不止一条。例如上面的例子中如果把V0→V3的距离改为3，那么从V0→V3就会有两条最短路径，即V0→V1→V3与V0→V3，它们都可以达到最短路径3。 于是，碰到这种有两条及以上可以达到最短距离的路径，题目就会给出一个第二标尺(第一标尺是距离)，要求在所有最短路径中选择第二标尺最优的一条路径。而第二标尺常见的是以下三种出题方法或其组合： ①给每条边再增加一个边权(比如说花费)，然后要求在最短路径有多条时要求路径上的花费之和最小(如果边权是其他含义，也可以是最大)。 ②给每个点增加一个点权(例如每个顶点能得到的权重)，然后在最短路径有多条时要求路径上的点权之和最大(如果点权是其他含义的话也可以是最小)。 ③直接问有多少条最短路径。 对这三种出题方法，都只需要增加一个数组来存放新增的边权或点权或最短路径条数，然后在Dijkstra算法中修改优化d的那个步骤即可，其他部分不需要改动。下面对这三种出题方法对代码的修改给出解释： ①新增边权。以新增的边权代表花费为例，用 cost[u][v]表示u→v的花费(由题目输入)，并增加一个数组c[]，令从起点s到达顶点u的最少花费为c[u]，初始化时只有c[]为0、其余c[u]均为INF。这样就可以在d[u]+G[u][v] for(int v=0;v // 如果v未访问&&u能到达v if(vis[v]==false G[u][v] != INF){ if(d[u] + G[u][v] < d[v]){ //以u未终结点可以是d[v]更优 d[v] = d[u] + G[u][v]; c[v] = c[u] + cost[u][v]; } else if(d[u] + G[u][v] ==d[v] && c[u] + cost[u][v] < c[v]){ c[v] = c[u] + cost[u][v]; //最短距离相同时看能否使c[v]更优 } } } ②新增点权。以新增的点权代表顶点中能得到的权重为例，用 weight[u]表示城市u中的物资数目(由题目输入)，并增加一个数组w[]，令从起点s到达顶点u可以收集到的最大物资为w[u]，初始化时只有w[s]为 weight[s]、其余w[u]均为0。这样就可以在d[u]+G[u][v]w[v](即可以使s到v的最大物资数目更优)时更新w[v]。代码如下： for(int v=0;v // 如果v未访问&&u能到达v if(vis[v]==false G[u][v] != INF){ if(d[u] + G[u][v] < d[v]){ //以u未终结点可以是d[v]更优 d[v] = d[u] + G[u][v]; w[v] = w[u] + weight[v]; } else if(d[u] + G[u][v] ==d[v] && w[u] + weight[v] > w[v]){
w[v] = w[u] + weight[v]; //最短距离相同时看能否使w[v]更优
}
}
}
③)求最短路径条数。只需要增加一个数组num[]，令从起点s到达顶点u的最短路径条数为num[u]，初始化时只有num[u]为1、其余num[u]均为0。这样就可以在d[u]+G[u][v]
for(int v=0;v
// 如果v未访问&&u能到达v
if(vis[v]==false G[u][v] != INF){
if(d[u] + G[u][v] < d[v]){ //以u未终结点可以是d[v]更优 d[v] = d[u] + G[u][v]; num[v] = num[u]; } else if(d[u] + G[u][v] ==d[v]){ num[v] += num[u]; //最短距离相同时累加num } } } 以上就是Dikjstra的全部内容。