運籌學(xué)基礎(chǔ)及應(yīng)用-63

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

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

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

在網(wǎng)絡(luò)圖中求s到t的最短路。第一步從s出發(fā)，將Lss=0標(biāo)記在s旁邊的方框內(nèi)（表示點s已標(biāo)記）；第二步找出與s相鄰且距離最小的點，設(shè)為r，計算Lsr=Lss+dsr，并將結(jié)果標(biāo)記在r旁邊的方框內(nèi)（表示點r已標(biāo)記），同時標(biāo)記邊sr；第三步從已標(biāo)記的點出發(fā)，找出這些點的所有未標(biāo)記鄰點，分別計算已標(biāo)記點的方框數(shù)與其鄰點的距離之和，利用“疊加最小”的原則確定下一個被標(biāo)記點，設(shè)為p，并將最小的和標(biāo)記在p旁邊的方框內(nèi)（表示點p已標(biāo)記）,同時標(biāo)記相應(yīng)邊；第四步重復(fù)第三步，直到t得到標(biāo)記為止。SABCDET25241431755702447891413594最短路：SABEDT；最短距離：LST=13例1求圖中S到T的最短路及最短距離。V1V2V3V4V5V6V752276742136例2求圖中v1到v7的最短路。05277610練習(xí)：用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）}⑵構(gòu)造任意兩點間直接到達(dá)、或者最多經(jīng)過1個中間點到達(dá)的最短距離矩陣D（1）=dij（1）；即dij(1)為D(0)中第i行和第j行對應(yīng)元素之和的最小值D（1）=v1v2v3v4v5v6v7V10527126∞V250727410V327065410V47260328V512753013V66442104v7∞10108340其中dij（2）=min{dir（1）+drj（1）}⑶構(gòu)造任意兩點間最多可經(jīng)過3個中間點到達(dá)的最短距離矩陣D（2）=dij（2）；即dij(2)為D(1)中第i行和第j行對應(yīng)元素之和的最小值D（2）=v1v2v3v4v5v6v7V105277610V25072548V32706548V47260326V57553013V66442104v710886340說明：一般的對于D（k）=dij（k），其中dij（k）=min{dir（k-1）+drj（k-1）}，(k=0,1,2,3,…)最多可經(jīng)過2k-1個中間點收斂條件：當(dāng)D（k+1）=D（k）時，計算結(jié)束；設(shè)網(wǎng)絡(luò)圖有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時，計算結(jié)束。注意狄克斯屈拉算法矩陣算法優(yōu)點既可以求兩點之間的最短距離，又可以確定最短路求任意兩點之間的最短距離缺點求某兩點之間的最短距離不能確定相應(yīng)兩點之間的最短路例3下圖中v1—v7表示7個村子，需要聯(lián)合建立一所小學(xué)，已知各村小學(xué)生的人數(shù)分別為v1—30人，v2—40人，v3—25人，v4—20人，v5—50人，v6—60人，v7—60人。問：學(xué)校應(yīng)建在哪一個村子，可使學(xué)生總行程最少？V1V2V3V4V6V752276742136V5v1v2v3v4v5v6v7V105277610V25072548V32706548V47260326V57553013V66442104v710886340解：用矩陣算法得到任意兩個村子之間的最短距離如下：

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