Floyd_Warshall
Floyd_Warshall的原理是动态规划,三重for循环,时间复杂度是O( n^3)
使用条件:
通常可以在任何图中使用，包括有向图、带负权边的图。
算法描述：
Floyd-Warshall 算法用来找出每对点之间的最短距离，它用邻接矩阵来储存边。
1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3 dist[v][v] ← 0
4 for each edge (u,v)
5 dist[u][v] ← w(u,v) // the weight of the edge (u,v)
6 for k from 1 to |V|
7 for i from 1 to |V|
8 for j from 1 to |V|
9 if dist[i][j] > dist[i][k] + dist[k][j]
10 dist[i][j] ← dist[i][k] + dist[k][j]
11 end if
Floyd算法为什么把k放在最外层？
来自知乎大神的答案:
算法思考:
- 若st无法到达ed,那么dist[st][ed]==INF
- 如果要求判断是否存在负环,只需检查是否存在dist[i][i]是负数的顶点i 即可。
因为dist[i][i]初始化为0,如果存在负环,那么从绕着负环一直走,可以找到从i到i更短的路径。
畅通工程续
题意:
给出起点终点,求最短路
这题用 多源最短路径 解决 单源最短路径
#include <cstdio>
#include<string.h>
#define Min(a,b) a<b?a:b
using namespace std;
const int INF=0x3f3f3f3f;
int graph[210][210],src,ed,n,m;
void floyd_Warshall()
{
for(int k=0;k<n;k++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
graph[i][j]=Min(graph[i][j],graph[i][k]+graph[k][j]);
}
}
}
if(graph[src][ed]==INF) printf("-1\n");
else printf("%d\n",graph[src][ed]);
}
int main()
{
int u,v,val;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(graph,INF,sizeof(graph));
for(int i=0;i<n;i++)
graph[i][i]=0;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&val);
if(graph[u][v]>val)
{
graph[u][v]=val;
graph[v][u]=val;
}
}
scanf("%d %d",&src,&ed);
floyd_Warshall();
//printf("%d\n",INF);
}
}
