2017-07-27 22:21:04

writer：pprp

该算法的本质是动态规划，形式简单，复杂度高为O(n^3)；

d[i][j] = max(d[i][k]+d[k][j],d[i][j]);

采用的基本手段是松弛

适用：解决多源最短路径问题

---

 

代码如下：

#include 
     
      using namespace std;const int maxn = 200;int n,s,t;int a[maxn+1][maxn+1];void init(){    int m,u,v;    cin >> n >> m;    for(int i =1; i<=n; i++)        for(int j =1; j<=n; j++)            a[i][j] = -1;    for(int i = 1; i<=m; i++)        cin >> u >> v >> a[u][v];    cin >> s >> t;}void floyd(){    int i,j,k;    for(k=1; k<=n; k++)        for(i=1; i<=n; i++)            for(j=1; j<=n; j++)            {                if(a[i][k]!=-1&&a[k][j]!=-1)                    a[i][j] = min(a[i][j],a[i][k]+a[k][j]);            }}int main(){    init();    floyd();    cout << a[s][t]+a[t][s]<