運籌學基礎及應用-63

運籌學新疆農業(yè)大學數(shù)理學院主講黃華第六章圖與網絡分析§6.3最短路問題1、最短路問題從已知的網絡圖中找出兩點之間距離最短（即權和最?。┑穆?。2、相關記號（1）dij表示圖中兩個相鄰點i和j之間的距離（即權）。易見dii=0；約定：當i和j不相鄰時，dij=∞；（2）Lij表示圖中點i和j之間的最短距離（即最小權和）。易見Lii=0；

即在已知的網絡圖中，從給定點s出發(fā)，要到達目的地t。問：選擇怎樣的行走路線，可使總行程最短？3、狄克斯屈拉（Dijkstra）標號算法（1）適用范圍用于求某兩個點之間的最短距離。（2）原理

最短路上任何片段是最短路。v1v2v3v4v5（3）思想按離出發(fā)點s的距離由近至遠逐步標出最短距離Lsi以及最佳行進路線。SABCDET252414317557例1求圖中S到T的最短路及最短距離。（4）步驟

在網絡圖中求s到t的最短路。第一步從s出發(fā)，將Lss=0標記在s旁邊的方框內（表示點s已標記）；第二步找出與s相鄰且距離最小的點，設為r，計算Lsr=Lss+dsr，并將結果標記在r旁邊的方框內（表示點r已標記），同時標記邊sr；第三步從已標記的點出發(fā)，找出這些點的所有未標記鄰點，分別計算已標記點的方框數(shù)與其鄰點的距離之和，利用“疊加最小”的原則確定下一個被標記點，設為p，并將最小的和標記在p旁邊的方框內（表示點p已標記）,同時標記相應邊；第四步重復第三步，直到t得到標記為止。SABCDET25241431755702447891413594最短路：SABEDT；最短距離：LST=13例1求圖中S到T的最短路及最短距離。V1V2V3V4V5V6V752276742136例2求圖中v1到v7的最短路。05277610練習：用Dijkstra算法求下圖從v1到v6的最短距離及路線。v3v54v1v2v4v635222421v1到v6的最短路為：思考求圖中任意兩點之間的最短距離。V1V2V3V4V6V752276742136V54、矩陣算法

求任意兩點間最短距離的方法注意：D(0)是一個對稱矩陣，且對角線上的元素全是0.D（0）=v1v2v3v4v5v6v7V1052∞∞∞∞V250∞27∞∞V32∞07∞4∞V4∞27062∞V5∞7∞6013V6∞∞42106v7∞∞∞∞360V1V2V3V4V6V752276742136V5其中dij（1）=min{dir（0）+drj（0）}⑵構造任意兩點間直接到達、或者最多經過1個中間點到達的最短距離矩陣D（1）=dij（1）；即dij(1)為D(0)中第i行和第j行對應元素之和的最小值D（1）=v1v2v3v4v5v6v7V10527126∞V250727410V327065410V47260328V512753013V66442104v7∞10108340其中dij（2）=min{dir（1）+drj（1）}⑶構造任意兩點間最多可經過3個中間點到達的最短距離矩陣D（2）=dij（2）；即dij(2)為D(1)中第i行和第j行對應元素之和的最小值D（2）=v1v2v3v4v5v6v7V105277610V25072548V32706548V47260326V57553013V66442104v710886340說明：一般的對于D（k）=dij（k），其中dij（k）=min{dir（k-1）+drj（k-1）}，(k=0,1,2,3,…)最多可經過2k-1個中間點收斂條件：當D（k+1）=D（k）時，計算結束；設網絡圖有p個點，即最多有p-2個中間點，則2k-1-1<p-22k-1

k-1<log2(p-1)k∴k<log2(p-1)+1，即計算到k=lg(p-1)/lg2+1時，計算結束。注意狄克斯屈拉算法矩陣算法優(yōu)點既可以求兩點之間的最短距離，又可以確定最短路求任意兩點之間的最短距離缺點求某兩點之間的最短距離不能確定相應兩點之間的最短路例3下圖中v1—v7表示7個村子，需要聯(lián)合建立一所小學，已知各村小學生的人數(shù)分別為v1—30人，v2—40人，v3—25人，v4—20人，v5—50人，v6—60人，v7—60人。問：學校應建在哪一個村子，可使學生總行程最少？V1V2V3V4V6V752276742136V5v1v2v3v4v5v6v7V105277610V25072548V32706548V47260326V57553013V66442104v710886340解：用矩陣算法得到任意兩個村子之間的最短距離如下：

先將每一行的元素乘以該村子的學生人數(shù)，得到小學建在相應村子時，該村學生上學時單程所走的路程。再將每一列的元素累加，得到小學建在相應村子時，七個村子的學生上學時單程所走的總路程。小學建在下列村子時，七個村子的學生上學時單程所走的路程v1v2v3v4v5v6v7015060210210180300200028080200160320501750150125100