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

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

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

最短路上任何片段是最短路。v1v2v3v4v5（3）思想按離出發(fā)點(diǎn)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)（表示點(diǎn)s已標(biāo)記）；第二步找出與s相鄰且距離最小的點(diǎn)，設(shè)為r，計(jì)算Lsr=Lss+dsr，并將結(jié)果標(biāo)記在r旁邊的方框內(nèi)（表示點(diǎn)r已標(biāo)記），同時(shí)標(biāo)記邊sr；第三步從已標(biāo)記的點(diǎn)出發(fā)，找出這些點(diǎn)的所有未標(biāo)記鄰點(diǎn)，分別計(jì)算已標(biāo)記點(diǎn)的方框數(shù)與其鄰點(diǎn)的距離之和，利用“疊加最小”的原則確定下一個(gè)被標(biāo)記點(diǎn)，設(shè)為p，并將最小的和標(biāo)記在p旁邊的方框內(nèi)（表示點(diǎn)p已標(biāo)記）,同時(shí)標(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的最短路為：思考求圖中任意兩點(diǎn)之間的最短距離。V1V2V3V4V6V752276742136V54、矩陣算法

求任意兩點(diǎn)間最短距離的方法注意：D(0)是一個(gè)對稱矩陣，且對角線上的元素全是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)造任意兩點(diǎn)間直接到達(dá)、或者最多經(jīng)過1個(gè)中間點(diǎn)到達(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)造任意兩點(diǎn)間最多可經(jīng)過3個(gè)中間點(diǎn)到達(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個(gè)中間點(diǎn)收斂條件：當(dāng)D（k+1）=D（k）時(shí)，計(jì)算結(jié)束；設(shè)網(wǎng)絡(luò)圖有p個(gè)點(diǎn)，即最多有p-2個(gè)中間點(diǎn)，則2k-1-1<p-22k-1

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

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