如果一个图中带有“负权回路”那么这个图则没有最短路
Floyd算法
思路
用于求任意两点之间的最短路程
概括就是，从 i 号顶点到 j 号点只经过前k号点的最短路程，实质上是一种“动态规划”的思想
参考链接： 坐在马桶上学算法【墙裂推荐】
核心代码【只有五行】
#include<stdio.h>
int main()
{
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]
}
}
}
}
}
个人见解
- Floyd算法首先将每两个点之间的距离设为初始值；
- 然后再在相邻的两个点之间插入一个点，这是减小距离的唯一办法；
- 然后不断增加插入的点的个数；
- 【不过它的时间复杂度为n^3是个硬伤…不过有些数据小的题还是挺好用的】
在这里附上一道运用了Floyd算法的例题： 青云的机房组网方案（简单）
互质：公约数只有1的两个整数，叫做互质整数。公约数只有1的两个自然数，叫做互质自然数，后者是前者的特殊情形。
最大公约数：最大公因数，也称最大公约数，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b）。求最大公约数有多种方法，常见的有质因数分解法、辗转相除法等等。
公因数：如果 a,b 是非零整数，而整数 p 同时是 a,b 的因数，我们便把 p 叫做 a,b 的公因数。
哈哈这些概念我现在才搞清楚…
题目
青云现在要将 nn 个机房连成一个互相连通的网络。
工程师小王设计出一个方案：通过在 nn 个机房之间铺设 n-1n−1 条双向的光纤，将所有的机房连接。可以假设数据在两个机房之间的光纤传输需要 11 单位时间。每个机房 ii 有一个初始值 a_ia
i
，当两个机房的初始值之间互质时，我们认为这两个机房之间的传输性能是非常重要的。请帮小王计算出所有数值互质的机房对之间的传输时间之和。
输入格式
第一行输入一个正整数 nn，第二行输入 nn 个正整数 a_1...a_na
1
...a
n
，表示 nn 个机房的初始值。
接下来输入 n-1n−1 行，每行输入两个数 a,ba,b，表示机房 aa 和机房 bb 之间有一条双向网络管道。
对于简单版本：n \leq 500n≤500，1 \leq a_i \leq 501≤a
i
≤50；
对于中等版本：n \leq 10000n≤10000， 1 \leq a_i \leq 5001≤a
i
≤500；
对于困难版本：n \leq 100000n≤100000，a_i \leq 100000a
i
≤100000。
输出格式
输出一行，表示所有初始值互质的机房对的传输时间和。
样例输入
4
1 2 3 4
1 2
2 3
3 4
样例输出
8
AC代码
#include<stdio.h>
#include<algorithm>
#define INF 0x3f3f3f3f
#define maxn 505
using namespace std;
int gcd(int a,int b)
{
if(a<b) swap(a,b);
if(b == 0)
{
return a;
}
else
{
return gcd(b,a % b);
}
}
int main()
{
int n,ans = 0;
int x,y;
int init[maxn];
int dis[maxn][maxn];
scanf("%d",&n);
for(int i = 1;i<=n;i++)
{
scanf("%d",&init[i]);
}
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=n;j++)
{
if(i == j)
{
dis[i][j] = 0;
}
else
{
dis[i][j] = INF;
}
}
}
for(int i = 1;i<n;i++)
{
scanf("%d%d",&x,&y);
dis[x][y] = dis[y][x] = 1;
}
/***********Floyd*********/
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][j] = dis[i][k] + dis[k][j];
}
}
}
}
/***********Floyd*********/
for(int i = 1;i<=n;i++)
{
for(int j = i + 1;j<=n;j++)
{
if(gcd(init[i],init[j]) == 1)
{
ans += dis[i][j];
}
}
}
printf("%d\n",ans);
}
Dijsktra算法
思路
单源最短路径
- 先找出距离源点最近的一个点，更新dis[2];
- 以2号点为基准，找到它的所有出边，判断dis[3] > dis[2] + next[2][i],并更新dis[3];
- 以此类推；
核心代码
#include<stdio.h>
#define maxn 1024
#define INF 0x3f3f3f3f
int n,m;//点和边
int book[maxn];
int next[maxn][maxn];
int dis[maxn];
int main()
{
/***********Dijsktra******************\
for(int i = 1;i<=n-1;i++)
{
int minm = INF;
//找到距离源点最近的点
for(int j = 1;j<=n;j++)
{
if(book[j] == 0 && dis[j] < minm)
{
minm = dis[j];
//坐标点更换
int nowNode = j;
}
}
book[nowNode] = 1;//标记
for(int k = 1;k<=n;k++)
{
//判断有路可走
if(next[nowNode][k] < INF)
{
if(dis[k] > dis[nowNode] + next[nowNode][k])
{
dis[k] = dis[nowNode] + next[nowNode][k];
}
}
}
}
/***********Dijsktra******************\
}
时间复杂度为n^2，比起Floyd还是优化了不少的，但是还可以优化
【立个flag】下一篇写堆(heap)和对Dijsktra的优化
