Floyd_Warshall_多源最短路径

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);
    }
}