定義
從一個點出發,經過一條簡單路徑回到起點成為環.圖的最小環就是所有環中長度最小的。
套用
最小環問題一般出現在計算機科學領域，主要是解決競賽中的一些有關最小環的題目。
解決方法
樸素算法
令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 的循環,即可找到整個圖的最小環。
上面是對無向圖的情況
若是有向圖,只需稍作改動。注意考慮有向圖中 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 為
中間點的最短路,則我們可以將其拓展到求最小環
