Floyd_Warshall
Floyd_Warshall的原理是動態(tài)規(guī)劃,三重for循環(huán),時間復雜度是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
- 如果要求判斷是否存在負環(huán),只需檢查是否存在dist[i][i]是負數的頂點i 即可艳馒。
因為dist[i][i]初始化為0,如果存在負環(huán),那么從繞著負環(huán)一直走,可以找到從i到i更短的路徑憎亚。
暢通工程續(xù)
題意:
給出起點終點,求最短路
這題用 多源最短路徑 解決 單源最短路徑
#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);
}
}
