再话图算法—最短路

最近真是加把劲骑士。今天复习一下最短路径,即给定图计算从起点到终点的最短路径。常用算法有Dijsktra、Bellman-ford、SPFA、Floyd算法。

Dijsktra单源最短路

基本思想:设置已访问节点S,然后每次从V-S中选择离起点s的最短路径最小的节点u,之后以u为中介,调整s到从u经过能到达的所有顶点v的最短距离,执行n次即可。简单来说,就是每次选择未访问最短距离点,选择后借助这个点开放相关边,再借助相关边更新最短路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
const int MAXV=1000;
const int INF=0x3fffffff;

int n,G[MAXV][MAXV];
int dis[MAXC];
bool vis[MAXV]={false};

void Dijstra(int s) //s means source
{
fill(dis,dis+MAXV,INF); //慎用memset,fill为algorithm库提供的函数
dis[s]=0;

for(int i=0;i<n;i++) //重复n次
{
int u=-1,MIN=INF; //找到dis[u]最小
for(int j=0;j<n;j++) //找到u
{
if(vis[j]==false&&dis[j]<MIN)
{
u=j;
MIN=dis[j];
}
}

if(u==-1) return; //说明剩下的顶点和s不连通
vis[u]=true;
for(int v=0;v<n;v++)
{
//如果v没访问 且 u能到达v 且 能够达到更优的dis
if(vis[v]==false&&G[u][v]!=INF && dis[u]+G[u][v]<dis[v])
{
dis[v]=dis[u]+G[u][v];
//pre[v]=u
}
}
}
}

邻接链表版的就略了,它可以一定程度减小时间复杂度,降低空间开销。
以上只是求解了最短距离,并未求解最短路径。实际上,我们添加一个pre[MAXV]数组,其中pre[v]表示从起点到顶点v的最短路径上v的上一个前驱节点。初始时,pre[i]指向自身i。最后,在更新可更新边的时候,将pre[v]确定为本次循环确定的节点u。要访问路径,从最后一个节点递归访问即可。

1
2
3
4
5
6
7
8
void DFS(int s,int v) //从终点v开始递归
{
if(v==s){
printf("%d\n",s);return;
}
DFS(s,pre[v]);
printf("%d\n",v);
}

同时,dijsktra算法也有很多变体,比如最短路不止一条,往往会新增一个关于开销的量度:

  • 给每一条边新增一个另一个维度的边权,即除了距离,还有花费,希望路上少花点钱
  • 给每个点增加一个点权,希望能够搜集更多的物资
  • 直接问如果有,有几条
    对于这三种,增加一个数组来存放新增的边权或者点权或者最短路径条数,然后修改优化dis[v]那个步骤即可。以第一个情况为例:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    for(int v=0;v<n;v++)
    {
    if(vis[v]==false&&G[u][v]!=INF)
    {
    if(dis[u]+G[u][v]<dis[v])
    {
    dis[v]=dis[u]+G[u][v];
    cos[v]=cos[u]+cost[u][v]; //cos和dis一样,cost和G类似
    } else if(dis[u]+G[u][v]==dis[v]&&c[u]+cost[u][v]<cost[v])
    {
    cos[v]=cos[u]+cost[u][v];
    }
    }
    }

而数有几条最短路,新增一个数组num,令从起点s到达顶点u的最短路径条数为num[u],最初num[s]=1其他为0,而会引起多条最短路的情况是在u这个点可以平等选择多个点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int v=0;v<n;v++)
{
if(vis[v]==false&&G[u][v]!=INF)
{
if(dis[u]+G[u][v]<dis[v])
{
dis[v]=dis[u]+G[u][v];
num[v]=num[u];
}else if(d[u]+G[u][v]==d[v])
{
num[v]+=num[u];
}
}
}

Bellman-Ford&SPFA

一旦出现负边权,Dijsktra算法就会失效。BF算法主要思想是设置一个数组d用来存放最短距离,同时返回一个bool值:如果其中存在从源点可达的负环,那么返回false;否则返回true,此时d中存放的值就是最短距离。
BF
此时如果不存在从源点可达的负环那么d中所有值应该达到最优了,对所有边在判断一次,如果仍然可以松弛,就说明存在从源点可达的负环返回false。其复杂度是O(n*Edge).

1
2
3
4
5
for(each edge uTov)
{
if(d[u]+length[uTov]<d[v]) return false;
return true;
}

邻接链表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
struct Node{
int v,dis;
};
vector<Node> Adj[MAXV];
int n;
int d[MAXV];
bool Bellman(int s)
{
fill(d,d+MAXV,INF);
d[s]=0;

for(int i=0;i<n;i++) //循环n次
{
for(int u=0;u<n;u++) //遍历所有边
{
for(int j=0;j<Adj[u].size();j++)
{
int v=Adj[u][j].v;
int dis=Adj[u][j].dis;
if(d[u]+dis<d[v])
{
d[v]=d[u]+dis;
}
}
}
}
//判断负环
for(int u=0;u<n;u++)
{
for(int j=0;j<Adj[u].size();j++)
{
int v=Adj[u][j].v;
int dis=Adj[u][j].dis;
if(d[u]+dis<d[v])
{
return false;
}
}
}
return true;
}

BF算法主要是在O(VE)的E上开销太大了,但其中存在很多无意义操作,通过队列优化就得到了SPFA算法,复杂度降低为O(kE),k一般不超过2.
SPFA

弗洛伊德算法

全源最短路,囿于复杂度,一般一次能跑的节点不能超过200.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Floyd()
{
for(int k=0;k<n;k++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
//两者可达且可优化
if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][k]+dis[k][j]<dis[i][j])
{
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
}
}