1.可以带负权但是不能有负环
2.时间复杂度是O( n^3)比Dijkstra的O( n^2 )要慢
3.由于要用临接矩阵,和本身算法的复杂度,不能计算过于大量的数据1000以下应该还能过
例题:http://acm.hdu.edu.cn/showproblem.php?pid=1869
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=101;
const int inf=0x3f3f3f;
int e[N][N];
int main()
{
int i,n,q,m,a,b,l;
while(cin>>n>>m)
{
for(i=0;i<n;i++)
for(int j=0;j<n;j++)
i==j?e[i][j]=0:e[i][j]=inf;//本身置零,其他初始置无穷
while(m--)
{
cin>>a>>b;
e[a][b]=1;
e[b][a]=1;
}
int flag=0;
for(i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++) //e[j][k]=min(e[j][k],e[j][i]+e[i][k]);
if(e[j][i]+e[i][k]<e[j][k])
e[j][k]=e[j][i]+e[i][k]; //整个算法的核心，遍历经由每个点的路径长度,判断更新
for(i=0;i<n&&!flag;i++)
for(int j=0;j<n;j++)
if(e[i][j]>7) flag=1;
if(flag) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
return 0;
}
其他类似的题：
http://acm.hdu.edu.cn/showproblem.php?pid=1874 这道题读入的时候要比较 两个地方之间可能有多条路,取最小
