Cycle

Cycle

一條路徑(path)的起點和終點相同,就是一只「環」。

以另一種角度來看,兩點之間有兩條以上的路徑,也會形成一只環。

如果環上的點都不重複,則稱作「簡單環」。簡單環上的每個點都恰好連著兩條邊。

Weight

如果圖上的邊都擁有權重,一只環的權重就是環上的邊的權重總和。

Negative Cycle

權重為負值的環稱做「負環」。負環在很多演算法當中佔據要角,有機會將會為各位介紹偵測負環的演算法。

Minimum Ratio Cycle

Minimum Ratio Cycle

尚無中譯,暫譯「最小比率環」。一張圖每條邊有兩組權重,第一組權重可為任意值,第二組權重不可為負值;於是一只環也有兩組權重。最小比率環是「第一組權重除以第二組權重」最小的環,可能有許多只。

第一個想法:搜尋答案

找出圖上所有的環,比較各個環的比率之後,就得到最小比率環了。然而,要找出圖上所有的環,是不容易的事情。

逆向思考,直接搜尋比率,再來看圖上有哪些環符合比率吧!

第二個想法:除法化作減法

令邊的兩組權重標記為w1和w2,環的兩組權重標記為Σw1和Σw2,環的比率標記為r = Σw1÷Σw2。

我們想知道一只環的比率r是多少,也就是說我們想知道Σw1÷Σw2是多少,也就是說我們想知道Σw1會等於多少的r×Σw2──要是直接把Σw1與r×Σw2相減,亦可表示Σw1與r×Σw2的多寡關係:r太小就表示差值是正數,r剛剛好就表示差值是零,r太大就表示差值是負數。利用這種方式,原本難以分析的除法式子,就成了容易分析的減法式子了。

為了湊出這道減法式子,把原來權重為w1和w2的一條邊,改為權重為w1 - r×w2的一條邊。如此一來,環的權重就變成了Σ(w1 - r×w2) = Σw1 - r×Σw2,這就成了我們所要的減法式子。

現在只要設定好r,然後看看圖上有沒有零環,如果有零環就表示這個r是合理的比率值。

深入分析

設定好r之後,圖上究竟有哪些環?

一、如果圖上有負環:這個負環的權重Σ(w1 - r×w2) = Σw1 - r×Σw2 < 0,可推得Σw1÷Σw2 < r。也就是說找到了一個負環,比率比r還小。r不是最小比率環的比率,r小於最小比率環的比率。

二、如果圖上沒有負環,但有零環:可推得Σw1÷Σw2 = r。由於圖上沒有負環,所以r就是最小比率環的比率,這個零環就是最小比率環。

三、圖上沒有負環、沒有零環,但有正環:可推得Σw1÷Σw2 > r。也就是說圖上所有的環,比率都比r還大。r不是最小比率環的比率,r大於最小比率環的比率。

四、圖上沒有環:沒有環就不會有最小比率環。

至此,這個問題已變成搜尋最小比率環的比率,並判斷圖上有沒有負環的問題了。要判斷圖上有沒有負環,可以利用各種偵測負環的演算法。

Binary Search

比率太小就有負環,比率太大就沒有負環。所以可以用Binary Search找答案。

演算法

1. 搜尋最小比率環的比率r。
2. 把圖上的邊的兩組權重w1和w2,改為只有一組權重w1-r×w2,

X. 可使用Binary Search找出正確的比率r:
   圖上有負環表示r太小,圖上沒負環表示r太大,
   沒有負環只有零環表示r是正解。

時間複雜度

【待補文字】

計算最小比率環的比率

【待補程式碼】

找出一個最小比率環

【待補程式碼】

Minimum Mean Cycle

Minimum Mean Cycle

尚無中譯,暫譯「最小平均值環」。一張圖上每條邊都有權重,最小平均值環是「權重除以邊數」最小的環,可能有許多只。

最小平均值環也可以視作是最小比率環的特例,當每條邊的第二組權重都等於1的時候。

想法

可參考CLRS在Bellman-Ford Algorithm章節的練習題。大致上來說就是經過k條邊的最短路徑,路徑末端會繞行最小平均值環,以讓路徑長度增加最少。

【待補文字】

演算法

令V為圖上的所有點構成的集合,n為圖上的點數。
圖上任意取一個點作為起點,d(k, i)為起點走k條邊到達i的最短路徑。

                          d(n, i) - d(k, i)
平均權重 =  min     max   ─────────────────
          i屬於V  0≤k≤n-1       n - k

如果圖上有不連通的部分,可以使用最短路徑Johnson's Algorithm所提到的技巧,在圖上另外新增一個起點,並且增加起點連到圖上其他點的邊,其權重皆設為零。如此一來,圖上的每一個點都可以由起點走到,而且最小平均值環也不會改變。

時間複雜度

如果圖的資料結構使用adjacency matrix,時間複雜度是O(V^3);如果圖的資料結構使用adjacency lists,時間複雜度是O(VE)。

計算最小平均值環的平均權重(adjacency matrix)

找出一個最小平均值環

【待補程式碼】

UVa 11090