【正文】 dge flow: If G in the edge is not enough traffic, that is, , then G 39。in the building edge , Empowering。 edge of G if has been the flow, that is, , then G39。 in the building edge , to empower the . The establishment of the network by streaming, you can seek in this network to the Meeting Point source shortest path, as decided by flow path, and then in the original network by flow in this path. Here, the use of maximum flow algorithm is still the principle of increasing flow, but the cost must be selected by the smallest chain by stream flow. Calculation, there is a need to address the problem. This is the stream network by G 39。the right to have a negative side, thus labeling law can not be directly applied to find to of the shortest path, using the right of other negative side puting network approach to the shortest path to to find the shortest path, will greatly reduce the putational efficiency. In order to still use the labeling method to calculate the shortest path, each flow set up by the network to achieve the shortest path, the network G can be the right of an amendment to do so by the stream to build the network will not be a negative right side, and guarantee the shortest path does not change. This modified method described below. When the flow value is zero, the first built by the shortest path for flow network, the result of nonnegative right side, of course, can be used to calculate labeling law. In order to increase flow network after the establishment of a negative time is not right side of the approach taken is to have stream G edge (f (e) 0) the right to w (e) amendment to 0. To this end, each time a flow network obtained by the shortest path, the following puting G in the right side of the new Where , calculation of G 39。of the shortest path to when and the value of the label. For the first time if the shortest path is the flow path by the edge, then, according to the shortest path algorithm must have ,substituting into (*) type must.If rather than by the side of flow path, it must have: Into the (*)type, there . Shows that the first amendment to w (e), against either side, there are , and a stream side (by side chain flow), there will be. Calculated after each iteration, if , by the need to establish the network flow edge, edge weights that is, the right will not be a negative side. In addition, the calculation of each iteration with (*) fixes all the , it is not difficult to prove that to each path x to y, its all the same to increase the path length .Therefore, and will not be the shortest path to the amendment changes.附錄2 中文譯文 在介紹最大流問(wèn)題時(shí)，我們列舉了一個(gè)最大物資輸送流問(wèn)題。如果這個(gè)問(wèn)題的已知條件還包括每條邊運(yùn)送單位物資的費(fèi)用，那么怎樣運(yùn)送，才能得到最大運(yùn)輸量，并且輸送費(fèi)用最少,這便是所謂最小費(fèi)用最大流問(wèn)題。 在最大流的有關(guān)定義的基礎(chǔ)上，若每條有向邊除權(quán)數(shù)（表示邊容量）外還有另外一個(gè)權(quán)數(shù)（表示單位流所需費(fèi)用），并且已求得該網(wǎng)絡(luò)的最大流值為F， 那么最小費(fèi)用最大流問(wèn)題，顯然可用以 下線性模型加以描述： 滿足 ，對(duì)一切 ，對(duì)一切（最大流約束） （或 ) 解決最小費(fèi)用最大流問(wèn)題，一般有兩條途徑。一條途徑是先用最大流算法算出最大流，然后根據(jù)邊費(fèi)用，檢查是否有可能在流量平衡的前提下通過(guò)調(diào)整邊流量，使總費(fèi)用得以減少。只要有這個(gè)可能，就進(jìn)行這樣的調(diào)整。調(diào)整后，得到一個(gè)新的最大流。 然后，在這個(gè)新流的基礎(chǔ)上繼續(xù)檢查，調(diào)整。這樣迭代下去，直至無(wú)調(diào)整可能，便得到最小費(fèi)用最大流。這一思路的特點(diǎn)是保持問(wèn)題的可行性（始終保持最大流），向最優(yōu)推進(jìn)。另一條解決途徑和前面介紹的最大流算法思路相類(lèi)似，一般首先給出零流作為初始流。這個(gè)流的費(fèi)用為零，當(dāng)然是最小費(fèi)用的。然后尋找一條源點(diǎn)至匯點(diǎn)的增流鏈，但要求這條增流鏈必須是所有增流鏈中費(fèi)用最小的一條。如果能找出增流鏈，則在增流鏈上增流，得出新流。將這個(gè)流做為初始流看待，繼續(xù)尋找增流鏈增流。這樣迭代下去，直至找不出增流鏈，這時(shí)的流即為最小費(fèi)用最大流。這一算法思路的特點(diǎn)是保持解的最優(yōu)性（每次得到的新流都是費(fèi)用最小的流），而逐漸向可行解近（直至最大流時(shí)才是一個(gè)可行解）。 由于第二種算法和已介紹的最大流算法接近，且算法中尋找最小費(fèi)用增流鏈，可以轉(zhuǎn)化為一個(gè)尋求源點(diǎn)至匯點(diǎn)的最短路徑問(wèn)題，所以這里介紹這一算法。 在這一算法中，為了尋求最小費(fèi)用的增流鏈，對(duì)每一當(dāng)前流，需建立伴隨這一網(wǎng)絡(luò)流的增流網(wǎng)絡(luò)。例如圖 1 網(wǎng)絡(luò)G 是具有最小 費(fèi)用的流，邊旁參數(shù)為，而圖 2 即為該網(wǎng)絡(luò)流 的增流網(wǎng)絡(luò)G′。增流網(wǎng)絡(luò)的頂點(diǎn)和原網(wǎng)絡(luò)相同。 按以下原則建立增流網(wǎng)絡(luò)的邊：若G中邊流量未飽，即，則 中建邊，賦權(quán)；若中邊已有流量，即，則中建邊，賦權(quán)。建立增流網(wǎng)絡(luò)后，即可在此網(wǎng)絡(luò)上求源點(diǎn)至匯點(diǎn)的最短路徑，以此決定增流路徑，然后在原網(wǎng)絡(luò)上循此路徑增流。這里，運(yùn)用的仍然是最大流算法的增流原理，唯必須選定最小費(fèi)用的增流鏈增流。 計(jì)算中有一個(gè)問(wèn)題需要解決。這就是增流網(wǎng)絡(luò)中有負(fù)權(quán)邊，因而不能直接應(yīng)用標(biāo)號(hào)法來(lái)尋找至的最短路徑，采用其它計(jì)算有負(fù)權(quán)邊的網(wǎng)絡(luò)最短路徑的方法來(lái)尋找至的最短路徑，將大大降低計(jì)算效率。為了仍然采用標(biāo)號(hào)法計(jì)算最短路徑，在每次建立增流網(wǎng)絡(luò)求得最短路徑后,可將網(wǎng)絡(luò)的權(quán)做一次修正，使再建的增流網(wǎng)絡(luò)不會(huì)出現(xiàn)負(fù)權(quán)邊，并保證最短路徑不至于因此而改變。下面介紹這種修改方法。 當(dāng)流值為零，第一次建增流網(wǎng)絡(luò)求最短路徑時(shí)，因無(wú)負(fù)權(quán)邊，當(dāng)然可以采用標(biāo)號(hào)法進(jìn)行計(jì)算。為了使以后建立增流網(wǎng)絡(luò)時(shí)不出現(xiàn)負(fù)權(quán)邊，采取的辦法是將 G中有流邊的權(quán)修正為0。為此， 每次在增流網(wǎng)絡(luò)上求得最短路徑后，以下式計(jì)算中新的邊權(quán) 式中 計(jì)算的至最短路徑時(shí)和的標(biāo)號(hào)值。第一次求最短徑時(shí)如果是增流路徑上的邊， 則據(jù)最短 路徑算法一定有 ,代入(*)式必有 .。 如果不是增流路徑上的邊，則一定有： ，代入(*)式則有 。 可見(jiàn)第一次修正 w (e),后，對(duì)任一邊，皆有， 且有流 的邊（增流鏈上的邊），一定有。以后每次迭代計(jì)算若 ，增流網(wǎng)絡(luò)需建立邊，邊權(quán)數(shù)，即不會(huì)再出現(xiàn)負(fù)權(quán)邊。 此外，每次迭代計(jì)算用(*)式修正一切， 不難證明對(duì)每一條x至y的路徑而言，其路徑長(zhǎng)度都同樣增加。因此，x至y的最短路徑不會(huì)因?qū)Φ男拚l(fā)生變化。40