poj 无向图最小环问题详解，模板

poj 无向图最小环问题详解，模板

日期:2011-12-09 点击:50 来源: youngyangyang04 分享至:

无向图的最小环问题：

无向图的最小环的求法不可能和有向图的求法一样，因为在有向图中i 到j 和 j 到i 算是一个环，但在无向图中不是一个环，
如果直接用flody算法将会出错，有向图的环可以为2个顶点，而无向图的环至少要三个顶点；所以为了求无向图的最小环，我们采用的原理是：　枚举最大环中的连接点，更新环的权重；
比普通Floyd多出来的部分,主要利用到的原理是当处理到k时,所有以1 到k - 1为中间结点的最短路径都已经确定，则这时候的环为（i到j(1 < i, j <= k - 1)的最短路径） + 边（i, k） + 边（k, j）遍历所有的i, j找到上述式子的最小值即位k下的最小代价环
核心代码：
初始化
for(int i=0;i<105;i++)//105只不过是一个范围
{
for(int j=0;j<105;j++)
{
dis[i][j]=g[i][j]=inf;
p[i][j]=i;//用一个pre[i][j]记录j前面的一个顶点，初始化为i
}
}
void floyd()
{
min1=inf;
for(int k=1;k<=n;k++)
{
for(int i=1;i<k;i++)//因为我们是枚举最大编号的点，所以这里只需枚举编号小于k的电
{
for(int j=i+1;j<k;j++)
{
int temp=j;
if(dis[i][j]+g[i][k]+g[k][j]<min1)
{
t=0;
min1=dis[i][j]+g[i][k]+g[k][j];
while(temp!=i)//若i== temp的时候则表示找全了路径，最后将k点加入路径中
{
ans[t++]=temp;
temp=p[i][temp];
}
ans[t++]=i;
ans[t++]=k;
}
}
}
}
/////////////////////////////////////
更新整个图的最短路径
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
if(dis[i][k]+dis[k][j]<dis[i][j])
{
dis[i][j]=dis[i][k]+dis[k][j];//枚举k ，i到j的最短路径dis[i][j]与其连接点k形成的环小于当前最小值时，则更新最小值
之后更新以k为中间节点的最短路径
p[i][j]=p[k][j];//当出现需要更新的时候则将pre[i][j] = pre[k][j];
} }

Tags：

分享至:

poj 无向图最小环问题 详解，模板

Tags：