最小環問題

最小環是指在一個圖中，有n個節點構成的邊權和最小的環(n>=3)。

一般來說,最小環分為有向圖最小環和無向圖最小環。

基本介紹

• 中文名：最小環
• 領域：計算機科學

定義

從一個點出發,經過一條簡單路徑回到起點成為環.圖的最小環就是所有環中長度最小的。

套用

最小環問題一般出現在計算機科學領域，主要是解決競賽中的一些有關最小環的題目。

解決方法

樸素算法

令e(u,v)表示u和v之間的連邊，再令min(u,v)表示，刪除u和v之間的連邊之後，u和v之間的最短路

最小環則是：min(u,v) + e(u,v)

時間複雜度是EV²

傳統的解決方法：dijkstra

任意一個環的權值，我們都可以看成兩個有邊相連的結點i、j的直接距離加上i、j間不包含邊(邊i->j)的最短路徑。求最短路徑我們第一個想到的就是Dijkstra算法。而Dijkstra所求的是一個點到所有點的最短距離。用Dijkstra所求的i、j的最短距離一定是i、j的直接距離(如果i，j連通)，所以我們需要先將i、j的邊從圖中刪除(若i，j不連通，則不用刪除)，再用Dijkstra求新圖中i、j的最短距離即可。所以我們每次在圖中選取一條邊，把它從圖中刪掉．然後對刪掉的那條邊所對應的2點進行Dijkstra，也就是m次Dijkstra

floyd求最小環

在Floyd的同時，順便算出最小環。

Floyd算法保證了最外層循環到 k 時所有頂點間已求得以 0...k-1 為中間點的最短路徑。一
個環至少有 3 個頂點,設某環編號最大的頂點為 L ,在環中直接與之相連的兩個頂點編號
分別為 M 和 N (M,N < L),則最大編號為 L 的最小環長度即為 Graph(M,L) + Graph(N,L) +
Dist(M,N) ,其中 Dist(M,N) 表示以 0...L-1 號頂點為中間點時的最短路徑,剛好符合 Floyd
算法最外層循環到 k=L 時的情況,則此時對 M 和 N 循環所有編號小於 L 的頂點組合即
可找到最大編號為 L 的最小環。再經過最外層 k 的循環,即可找到整個圖的最小環。

int mincircle = infinity;Dist = Graph;for(int k=0;k<nVertex;++k){//新增部分:for(int i=0;i<k;++i)for(int j=0;j<i;++j)mincircle = min(mincircle,Dist[i][j]+Graph[j][k]+Graph[k][i]);//通常的 floyd 部分:for(int i=0;i<nVertex;++i)for(int j=0;j<i;++j){int temp = Dist[i][k] + Disk[k][j];if(temp < Dist[i][j])Dist[i][j] = Dist[j][i] = temp;}}

上面是對無向圖的情況

若是有向圖,只需稍作改動。注意考慮有向圖中 2 頂點即可組成環的情況

例題講解

HDU-杭州旅遊

Description

杭州有 N 個景區， 景區之間有一些雙向的路來連線， 現在 8600 想找一條旅遊路線， 這個路線從 A 點出發並且最後回到 A 點。
假設經過的路線為 V1,V2,....VK,V1,那么必須滿足 K>2,就是說至除了出發點以外至少要經過 2 個其他不同的景區， 而且不能重複經過同一個景區。 現在 8600 需要你幫他找一條這樣的路線， 並且花費越少越好。

Input

第一行是 2 個整數 N 和 M（ N <= 800, M <= 600000)， 代表景區的個數和道路的條數。
接下來的 M 行里， 每行包括 3 個整數 a,b,c.代表 a 和 b 之間有一條通路， 並且需要花費c 元(c <= 10000)。

Output

如果能找到這樣一條路線的話， 輸出花費的最小值。 如果找不到的話， 輸出 "It'simpossible." (沒有雙引號)

Sample Input

輸入樣例1：
3 3
1 2 1
2 3 1
1 3 1

輸入樣例2：
3 3
1 2 1
1 2 3
2 3 1

Sample Output

輸出樣例1：
3

輸出樣例2：
It's impossible.

Hint

對於 40%的數據： 2 <= n < 100, m<=10000
對於 100%的數據： n <= 800, m<=600000

分析:

加入有一個環,其編號最大的點為 L,那么這個環可以看為 L 與其相鄰的兩個點 A 和
B 與 A 到 B 的最短路上的點(編號均小於 L 的最短路)。
考慮 floyd 算法,由於該算法每次都是求出了 1 到 k−1 做為中間點的最短路然後來求已 k 為
中間點的最短路,則我們可以將其拓展到求最小環

標程

#include<iostream>#include<cstdlib>#include<cstdio>#include<cmath>using namespace std;const int MAXN=810;const int INF=214748364;int gi[MAXN][MAXN];int map[MAXN][MAXN];int n,m;int ans=INF;int main(){  int a,b,c;  scanf("%d%d",&n,&m);  for(int i=0;i<=n;i++)    for(int j=0;j<=n;j++)      {        if( i==j )          gi[ i ][ j ]=map[ i ][ j ]=0;        else          gi[ i ][ j ]=map[ i ][ j ]=INF;      }  for(int i=1;i<=m;i++)    {      scanf("%d%d%d",&a,&b,&c);      if( map[ a ][ b ]>c )        gi[ a ][ b ]=map[ a ][ b ]=gi[ b ][ a ]=map[ b ][ a ]=c;    }  for(int k=1;k<=n;k++)    {      for(int i=1;i<=k-1;i++)        for(int j=i+1;j<=k-1;j++)          ans=min( ans,gi[ i ][ k ]+gi[ k ][ j ]+map[ i ][ j ]);      for(int i=1;i<=n;i++)        for(int j=1;j<=i-1;j++)          if( j!=k && i!=k )            map[ j ][ i ]=map[ i ][ j ]=min( map[ i ][ k ]+map[ k ][ j ],map[ i ][ j ]);    }  if( ans>=INF )    printf("It's impossible.\n");  else    printf("%d\n",ans);  return 0;}