UC知道求无向带全图的最小环（pascal语言）
来源：百度知道 编辑：UC知道 时间：2024/06/18 00:32:20
【参考程序】
const maxn=30;
var
n：integer;
dist:array[1..maxn,1..maxn]of double;
procedure init;
var m,i,u,v:integer;
begin
readln(n,m);
for u:=1 to n do
dist[u,v]:=1e100;
for i:=1 to m do
begin
read(u,v,dist[u,v]);
dist[v,u]:=dist[u,v];
end;
procedure main;
var
i,j,k:integer;
min:double;
begin
min:=1e100;
for k:=1 to n do
begin
for j:=i+1 to k-1 do
if(dist[i,j]+dist[i,k]+dist[k,j]<min)then
min:=dist[i,j]+dist[i,k]+dist[k,j];
for i:=1 to n do
for j:=1 to n do
if (dist[i,k]+dist[k,j]<dist[i,j])then
dist[i,j]:=dist[i,k]+dist[k,j];
end;
if (min>1e99)then
writeln('No circle.')
else
writeln('Length=',min:0:0);
end;
beg
const maxn=30;
var
n：integer;
dist:array[1..maxn,1..maxn]of double;
procedure init;
var m,i,u,v:integer;
begin
readln(n,m);
for u:=1 to n do
dist[u,v]:=1e100;
for i:=1 to m do
begin
read(u,v,dist[u,v]);
dist[v,u]:=dist[u,v];
end;
procedure main;
var
i,j,k:integer;
min:double;
begin
min:=1e100;
for k:=1 to n do
begin
for j:=i+1 to k-1 do
if(dist[i,j]+dist[i,k]+dist[k,j]<min)then
min:=dist[i,j]+dist[i,k]+dist[k,j];
for i:=1 to n do
for j:=1 to n do
if (dist[i,k]+dist[k,j]<dist[i,j])then
dist[i,j]:=dist[i,k]+dist[k,j];
end;
if (min>1e99)then
writeln('No circle.')
else
writeln('Length=',min:0:0);
end;
beg
朴素算法
令e(u,v)表示u和v之间的连边，再令min(u,v)表示，删除u和v之间的连边之后，u和v之间的最短路
最小环则是min(u,v) + e(u,v)。时间复杂度是EV2。
改进算法
在floyd的同时，顺便算出最小环
g[i][j]=i,j之间的边长
dist:=g;
for k:=1 to n do
begin
for i:=1 to k-1 do
for j:=i+1 to k-1 do
answer:=min(answer,dist[i][j]+g[i][k]+g[k][j]);
for i:=1 to n do
for j:=1 to n do
dist[i][j]:=min(dist[i][j],dist[i][k]+dist[k][j]);
end;
最小环改进算法的证明
一个环中的最大结点为k(编号最大)，与他相连的两个点为i,j，这个环的最短长度为g[i][k]+g[k][j]+i到j的路径中,所有结点编号都小于k的最短路径长度。根据floyd的原理，在最外层循环做了k-1次之后，dist[i][j]则代表了i到j的路径中，所有结点编号都小于k的最短路径
综上所述，该算法一定能找到图中最小环。