gaomaoqi2022
2020-03-31 18:40:20
对在有权图
简单讲:找出连接两个给定顶点权值和最小的路径。
SSSP:求给定起点S到其他所有点的最短路,常见算法有Dijkstra算法、Bellman_Ford算法及SPFA算法;
APSP:求任意两对顶点之间的最短路,常见算法有Floyd算法;
这两种情况在做题时一定要分清
Floyd算法借助DP思想,可以求出每对点之间的最短距离,它对于图的要求是,可以是无向图和有向图,边权可正可负,唯一的要求是不能有负环。
定义
它有两种情况:
综合起来,状态转移方程为:
边界条件:
具体来说就是:初始
非常简单粗暴,时间复杂度:
for(k=1;k<=n;k++) //枚举中间点
for(i=1;i<=n;i++) //枚举起点
for(j=1;j<=n;j++) //枚举终点
if((d[i][k]!=INF)&&(d[k][j]!=INF)&&(d[i][k]+d[k][j]<d[i][j]))
d[i][j]=d[i][k]+d[k][j];
Description
图的直径是这样定义的:在一个带正权的图中,它的直径是指任意两点之间最短路的最大距离。注意:此图为无向图。
Input
第一行有两个正整数N,M,分别表示点数和边数(N<=100,M<=10000)。
接下来M行,每行三个正整数,分别表示每一条边的两个端点编号和长度。
Output
输出只有一行为这个图的直径。
Sample Input
3 3
1 2 1
2 3 2
1 3 2
Sample Output
2
这显然是APSP,即任意两对顶点之间的最短路
代码实现:
由于上面已经说的很清楚了,所以代码里面没有太多注释
#include<iostream>
#include<cstdio>
#define maxn 5003
#define yao_bu_ke_ji 0x3f3f3f3f
using namespace std;
int n,m;
int fd[maxn][maxn];
int floyed() {
for(int mid=1; mid<=n; mid++) {
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(fd[i][mid]<yao_bu_ke_ji-5&&fd[mid][j]<yao_bu_ke_ji-5) {
fd[i][j]=min(fd[i][j],fd[i][mid]+fd[mid][j]);
}
}
}
}
}
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(i==j) fd[i][j]=0;
else fd[i][j]=yao_bu_ke_ji;
}
}
for(int i=1; i<=m; i++) {
int x,y;
cin>>x>>y;
cin>>fd[x][y];//cin要 分开写! 分开写! 分开写!
fd[y][x]=fd[x][y];
}
floyed();
int ans=-yao_bu_ke_ji;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(fd[i][j]<yao_bu_ke_ji-3) ans=max(ans,fd[i][j]);
}
}
cout<<ans<<endl;
return 0;
}
现准备在n个居民点v1,v2,...,vn中设置一银行,问设在哪个点,可使最大服务距离最小?
若设置两个银行,问设在哪两个点?
假设各个居民点都有条件设置银行,并有路相连,且路长已知。实质就是求图的中心问题。
设置一个银行的情况:
初始化
读入数据,邻接矩阵存储;
用Floyd求任意两点间的最短距离
枚举点
#include<iostream>
#include<cstdio>
#define maxn 6120
#define sky 0x7fffffff/2
using namespace std;
int n,m;
int fd[maxn][maxn];
void floyed() {
for(int mid=1; mid<=n; mid++) {
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(fd[i][mid]<sky-3&&fd[mid][j]<sky-3) {
fd[i][j]=min(fd[i][j],fd[i][mid]+fd[mid][j]);
}
}
}
}
}
int main() {
cin>>n;
m=n-1;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(i==j) fd[i][j]=0;
else fd[i][j]=sky;
}
}
for(int i=1; i<=m; i++) {
int x,y;
cin>>x>>y;
cin>>fd[x][y];
fd[y][x]=fd[x][y];
}
floyed();
int anss[maxn];
for(int i=1; i<=n; i++) {
int ans=-sky;
for(int j=1; j<=n; j++) {
if(fd[i][j]<sky-3) ans=max(ans,fd[i][j]);
}
anss[i]=ans;
}
int reans=sky,aans;
for(int i=1; i<=n; i++) {
// reans=min(anss[i],reans);
if(anss[i]<reans) {
reans=anss[i];
aans=i;
}
}
cout<<aans;
return 0;
}
设置两个银行的情况
代码走丢了
如果图是不带负权的有向图或者无向图,我们可以用类似Prim算法的贪心思想,从起点
算法实现时,用一维数组
初始化
经过
A. 选择一个未标记的点
B. 标记点
C. 以