求无向图最小环算法-floyd
floyd算法。
有 i 出发返回 i 的最小环=min{d[i][j]+map[i][k]+map[k][j]};
for(k=1；k<=n；k++)
{ for(i=1；i<k；i++)
for(j=i+1；j<k；j++)
if(d[i][j]+m[i][k]+m[k][j]<min)
min=d[i][j]+m[i][k]+m[k][j]；
for(i=1；i<=n；i++)
for(j=1；j<=n；j++)
if(d[i][k]+d[k][j]<d[i][j])
d[i][j]=d[i][k]+d[k][j]；
}根据floyd算法的性质，k 时，d[i][j]中间点小于 k，所以 d[i][j]不可能与 map[i][k]+map[k][j] 重路。