最短路径算法之Dijkstra

最短路径问题的定义

· 对任意给出的图G(V,E)和起点S,终点T,如何求从S到T的最短路径(这条路径上经过的所有边的边权之和最小)
· 解决最短路径问题常用的算法有Dijkstra算法、Bellman-Ford算法、SPFA算法和Floyd算法,此篇介绍Dijkstra算法

Dijkstra算法

· 用来解决单源最短路径问题,即给定图G和起点,通过算法得到该起点s到达其他每个顶点的最短距离。
· 基本思想:
1.对图G(V,E)设置集合S,存放已被访问的顶点,每次从集合V-S中选择与起点s的最短距离最小的一个顶点(记为u),访问并加入集合S。
2.之后,令顶点u为中介点,优化起点s与所有从u能到达的顶点v之间的最短距离。
3.这样的如上操作执行n次(n为顶点数),直到集合S包含所有的顶点。
· 实际操作中,集合S用bool数组对元素进行访问标识来操作
· 另设置一int数组d[]表示起点s到达顶点Vi的最短距离。初始设置d[s]=0,d[else]=INF(极大值)

代码实现

伪代码

1
2
3
4
5
6
7
8
9
10
11
Dijkstra(G,d[],s){
初始化;
for(循环n次){
u=使d[u]最小的还未被访问的顶点的编号;
记u已被访问;
for(从u出发能到达的所有顶点v){
if(v未被访问&&以u为中介点使s到v的d[v]更优)
优化d[v];
}
}
}

邻接矩阵版实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int n,G[MAXV][MAXV];
int d[MAXV];
bool vid[MAXV]={false};
void Dijkstra(int s){
fill(d,d+MAXV,INF);
d[s]=0;
for(int i=0;i<n;i++){
int u=-1,MIN=INF;
for(int j=0;j<n;j++){ //找到未访问顶点中d[u]最小的u
if(vis[j]==false&&d[j]<MIN){
u=j;
MIN=d[j];
}
}
if(u==-1) return; //找不到小于INF的d[u],说明剩下的顶点与s不连通
vis[u]=true;
for(int v=0;v<n;v++){
if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]){
d[v]=d[u]+G[u][v];
}
}
}
}

如何记录最短路径

增设pre[]数组,在优化d[v]的同时记v的前驱结点为u:

1
2
3
4
if(v未被访问&&以u为中介点使s到v的d[v]更优){
d[v]=d[u]+G[u][v]; //优化d[v];
pre[v]=u; //令v的前驱为u;
}

最后采用DFS对数组pre[]递归得到最短路径:

1
2
3
4
5
6
7
8
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); //从最深出返回后输出每一层
}

最短路径增加第二标尺

1.新增边权(如路上花费最小)
2.新增点权,点权和最大(如PATA1087中城市幸福值最大)
3.求最短路径条数
1和2均在优化d[v]时添加相应判断即操作即可,3则需增加一个数组num[],初始化num[s]=1,num[else]=0:

1
2
3
4
5
6
7
8
9
10
for(int v=0;v<n;v++){
if(vis[v]==false&&G[u][v]!=INF){
if(d[u]+G[u][v]<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];
}
}
}

Dijkstra+DFS的方法求第二标尺下的最优路径

1.先在Dijkstra算法中记录下所有的最短路径

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> pre[MAXV];  //记录路径

for(int v=0;v<n;v++){
if(vis[v]==false&&G[u][v]!=INF){
if(d[u]+G[u][v]<d[v]){
d[v]=d[u]+G[u][v];
pre[v].clear(); //更短路径下之前记录的v点前驱务必先clear
pre[v].push_back(u);
}else if(d[u]+G[u][v]==d[v]){
pre[v].push_back(u);
}
}
}

2.通过DFS从这些最短路径中选出一条第二标尺最优的路径
方法:
第一步中生成的pre[]相当于一棵树,选定根结点v(即终点)进行dfs,每次到达叶子结点(即起点),就会产生一条完整的最短路径,计算其第二标尺值
需添加:
· 作为全局变量的第二标尺最优值optValue
· 记录最优路径的数组path(用vector存)
· 临时记录DFS遍历到叶子结点时的路径tempPath

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int optValue;
vector<int> path,tempPath;

void DFS(int v){ //当前访问结点v
if(v==s){
tempPath.push_back(v);
int value;
//此处计算tempPath上的value值
//由于temppath中的路径结点是逆序的
//访问最好倒着进行
if(value优于optValue){
optValue=value;
path=tempPath;
}
tempPath.pop_back();
return;
}
tempPath.push_back(v);
for(int i=0;i<pre[v].size();i++){
DFS(pre[v][i]);
}
tempPath.pop_back();
}