【OI之路】03图论算法-2最短路之全源最短路(Floyd)

3.2.1定义

这个算法用于求所有点对的最短距离,时间复杂度为O(n^3)。【无法判断、计算含有负环的图】

依次扫描每一点(k),并以该点作为中介点,计算出通过k点的其他任意两点(i,j)的最短距离,这就是floyd算法的精髓!同时也解释了为什么k点这个中介点要放在最外层循环。

其实就是运用动态规划的思想。

3.2.2 代码

1
2
3
4
5
6
7
8
9
10
void floyd()
{
memset(dis,127,sizeof(dis));
for(int i=1;i<=n;i++) dis[i][i]=0;
for(int k=1;k<=n;k++)//中介点
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}

up 2018.8.29
floyd的正确性证明:
设$dis[k][i][j]$表示只经过编号小于k的点,从i到j的最小距离
那么对于任意一条最短路径,可以想象为分割的,
然后以k为阶段,长度递增,逐渐合并
具体实现的时候,只要把k放在外面,就可以通过滚动数组,省去第一维

找无向图最小环:
加入一句

1
ans=min(dis[i][j]+dis[i][k]+dis[k][j]);

即可
韵味自行理解
其实就是假设这个环,编号最大那个为k
不过要注意一点,就是要针对实际需求,看要不要打上i!=j等三个条件
例题:
poj1734 Sightseeing trip

然后无向图的话,因为两个点也能组成(甚至一个点)
所以不需要对环的大小作限制,可以直接扫一次dis[i][i]
例题:vijos1423

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
42
43
44
45
46
47
48
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int MAX_N=210;
const int INF=0x3f3f3f3f;
int w[MAX_N];
int dis[MAX_N][MAX_N];
void main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
memset(dis,63,sizeof dis);
while(m--)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);c+=w[x];
if(c<dis[x][y]) dis[x][y]=c;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=dis[i][k]+dis[k][j];
printf("%d ",dis[1][1]==INF?-1:dis[1][1]);
}
};
int main()
{
mine::main();
}

当然如果跑dijkstra+heap
把起点更新后,d[st]=正无穷,下一次取出也是最小环长度

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/a73f.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%