一种比较差的办法是一次dijkstra后，删除一条边，然后再进行一次，效率很低。
我们可以借助Floyd的变形在O(n^3)内解决次问题。
在floyd的同时，顺便算出最小环g[i][j]=i,j之间的边长
1 dist:=g;
2 for k:=1 to n do
3 begin
4 for i:=1 to k-1 do
5 for j:=i+1 to k-1 do
6 answer:=min(answer,dist[i][j]+g[i][k]+g[k][j]);
7 for i:=1 to n do
8 for j:=1 to n do
9 dist[i][j]:=min(dist[i][j],dist[i][k]+dist[k][j]);
10 end;
2 for k:=1 to n do
3 begin
4 for i:=1 to k-1 do
5 for j:=i+1 to k-1 do
6 answer:=min(answer,dist[i][j]+g[i][k]+g[k][j]);
7 for i:=1 to n do
8 for j:=1 to n do
9 dist[i][j]:=min(dist[i][j],dist[i][k]+dist[k][j]);
10 end;
最小环改进算法的证明
一个环中的最大结点为k(编号最大)，与他相连的两个点为i,j，这个环的最短长度为g[i][k]+g[k][j]+i到j的路径中,所有结点编号都小 于k的最短路径长度。根据floyd的原理，在最外层循环做了k-1次之后，dist[i][j]则代表了i到j的路径中，所有结点编号都小于k的最短路 径
综上所述，该算法一定能找到图中最小环。
转自http://mces89.yo2.cn/articles/%E6%B1%82%E6%9C%80%E5%B0%8F%E7%8E%AF%E9%97%AE%E9%A2%98.html