【正文】 離 …… 經(jīng)有限次迭代可求出 vi 到 vj 的最短距離； 福德方法：適用于有負權(quán)系數(shù)，但無負回路的有向或無向網(wǎng)絡(luò)的最短路問題，能求出起點 v1 到所有其它點 vj 的最短距離。 Min L(?) = ? lij ?為從 v1 到 vn 的通路； lij?? 其中， lij為從 vi 到 vj 的一步距離。給定 D中一個起點 和 終點，設(shè) P是 D中從 到 的一條路 .則定義路 P的權(quán)是 P中所有弧的權(quán)之和 .記為 ，即 又若 P*是 D圖中 到 的一條路，且滿足 則稱 P*為從 到 的最短路。不妨設(shè)此弧為（ Vc,Vd），則給此弧的終點以雙標(biāo)號（ scd,c） ,返回步驟 2。 4. 對上述弧的集合中的每一條弧，計算 sij=li+cij 。如果 vt 未標(biāo)號，則可以斷言不存在從 vs到 vt的有向路。 解最短路的 Dijkstra算法 (雙標(biāo)號法） 步驟： V1以標(biāo)號 (0,s) I，沒標(biāo)號的點的集合 J以及弧的集合 3. 如果上述弧的集合是空集，則計算結(jié)束。 2 最短路問題 ? 最短路問題：對一個賦權(quán)的有向圖 D中的指定的兩個點 Vs和 Vt找到一條從 Vs 到 Vt 的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱之為從 Vs到 Vt的最短路。 ? 網(wǎng)絡(luò)： 在賦權(quán)的有向圖 D中指定一點，稱為發(fā)點，指定另一點稱為收點，其它點稱為中間點，并把 D中的每一條弧的賦權(quán)數(shù)稱為弧的容量， D就稱為網(wǎng)絡(luò)。 ? 回路： 若路的第一個點和最后一個點相同，則該路為回路。 ? 有向圖： 由點和弧構(gòu)成的圖，記作 D=（ V， A）。 管 理 運 籌 學(xué) 25 167。下圖就是一個反映這七人“認識”關(guān)系的圖。 (v1) 趙 (v2)錢 孫 (v3) 李 (v4) 周 (v5) 吳 (v6) 陳 (v7) e2 e1 e3 e4 e5 管 理 運 籌 學(xué) 24 167。 (v1) 趙 (v2)錢 (v3)孫 (v4)李 (v5) 周 (v6)吳 (v7)陳 e2 e1 e3 e4 e5 管 理 運 籌 學(xué) 23 167。 1 圖與網(wǎng)絡(luò)的基本概念 圖論中圖是由點和邊構(gòu)成，可以反映一些對象之間的關(guān)系。 管 理 運 籌 學(xué) 1 2 3 7 6 4 5 管 理 運 籌 學(xué) 1 2 3 7 6 4 5 管 理 運 籌 學(xué) 哈密頓 （ Hamilton） 回路是十九世紀(jì)英國數(shù)學(xué)家哈密頓提出 ， 給出一個正 12面體圖形 ， 共有 20個頂點表示 20個城市 ， 要求從某個城市出發(fā)沿著棱線尋找一條經(jīng)過每個城市一次而且僅一次 ， 最后回到原處的周游世界線路 （ 并不要求經(jīng)過每條邊 ） 。 管 理 運 籌 學(xué) 1 2 3 7 6 4 5 管 理 運 籌 學(xué) 1 2 3 7 6 4 5 管 理 運 籌 學(xué) 假定第二次就座方案是 （ 1， 3， 5， 7， 2， 4， 6， 1） ，那么第三次就座方案就不允許這些頂點之間繼續(xù)相鄰 ， 只能從圖中刪去這些邊 。 管 理 運 籌 學(xué) A C B D 管 理 運 籌 學(xué) 有 7個人圍桌而坐 ， 如果要求每次相鄰的人都與以前完全不同 ， 試問不同的就座方案共有多少種 ？ 用頂點表示人 ， 用邊表示兩者相鄰 ， 因為最初任何兩個人都允許相鄰 ， 所以任何兩點都可以有邊相連 。 管 理 運 籌 學(xué) 例 101： 哥尼斯堡七橋問題 哥尼斯堡 （ 現(xiàn)名加里寧格勒 ）是歐洲一個城市 ， Pregei河把該城分成兩部分 ， 河中有兩個小島 ， 十八世紀(jì)時 ， 河兩邊及小島之間共有七座橋 ， 當(dāng)時人們提出這樣的問題：有沒有辦法從某處 （ 如 A） 出發(fā) ，經(jīng)過各橋一次且僅一次最后回到原地呢 ？ 管 理 運 籌 學(xué) A B C D 管 理 運 籌 學(xué) 最后 ， 數(shù)學(xué)家 Euler在 1736年巧妙地給出了這個問題的答案 ， 并因此奠定了圖論的基礎(chǔ) ， Euler把 A、B、 C、 D四塊陸地分別收縮成四個頂點 ， 把橋表示成連接對應(yīng)頂點之間的邊 ， 問題轉(zhuǎn)化為從任意一點出發(fā) ， 能不能經(jīng)過各邊一次且僅一次 ，最后返回該點 。 6 統(tǒng)籌法（網(wǎng)絡(luò)規(guī)劃） 管 理 運 籌 學(xué) 圖論是專門研究圖的理論的一門數(shù)學(xué)分支 ， 屬于離散數(shù)學(xué)范疇 ，與運籌學(xué)有交叉 ， 它有 200多年歷史 ，大體可劃分為 三個階段 ： 第一階段是從十八世紀(jì)中葉到十九世紀(jì)中葉 ，處于萌芽階段 ， 多數(shù)問題為游戲而產(chǎn)生 ， 最有代表性的工作是所謂的Euler七橋問題 (1736年 )， 即一筆畫問題 。 4 最大流問題 167。 2 最短路問題 167。管 理 運 籌 學(xué) 1 第五章 圖與網(wǎng)絡(luò)模型 167。 1 圖與網(wǎng)絡(luò)的基本概念 167。 3 最小生成樹問題 167。 5 車間作業(yè)計劃 167。 管 理 運 籌 學(xué) 第二階段 是從十九世紀(jì)中葉到二十世紀(jì)中葉 ， 這時 ， 圖論問題大量出現(xiàn) ， 如 Hamilton問題 ， 地圖染色的四色問題以及可平面性問題等 ， 這時 ， 也出現(xiàn)用圖解決實際問題 ， 如 Cayley把樹應(yīng)用于化學(xué)領(lǐng)域 ， Kirchhoff用樹去研究電網(wǎng)絡(luò)等 . 管 理 運 籌 學(xué) 第三階段 是二十世紀(jì)中葉以后 ， 由生產(chǎn)管理 、 軍事 、 交通 、 運輸 、 計算機網(wǎng)絡(luò)等方面提出實際問題 ， 以及大型計算機使大規(guī)模問題的求解成 為 可 能 ， 特 別 是 以 Ford 和Fulkerson建立的網(wǎng)絡(luò)流理論 ， 與線性規(guī)劃 、 動態(tài)規(guī)劃等優(yōu)化理論和方法相互滲透 ， 促進了圖論對實際問題的應(yīng)用 。 這就是著名的 Euler問題 。 管 理 運 籌 學(xué) 1 2 3 7 6 4 5 管 理 運 籌 學(xué) 假定第一次就座方案是 （ 1， 2， 3， 4， 5， 6， 7， 1） ，那么第二次就座方案就不允許這些頂點之間繼續(xù)相鄰 ， 只能從圖中刪去這些邊 。 管 理 運 籌 學(xué) 1 2 3 7 6 4 5 管 理 運 籌 學(xué) 1 2 3 7 6 4 5 管 理 運 籌 學(xué) 假定第三次就座方案是 （ 1， 4， 7， 3， 6， 2， 5， 1） ，那么第四次就座方案就不允許這些頂點之間繼續(xù)相鄰 ， 只能從圖中刪去這些邊 ， 只留下 7點孤立點 ， 所以該問題只有三個就座方案 。 管 理 運 籌 學(xué) 管 理 運 籌 學(xué) 22 167。 例如：在一個人群中，對相互認識這個關(guān)系我們可以用圖來表示，下圖就是一個表示這種關(guān)系的圖。 1 圖與網(wǎng)絡(luò)的基本概念 當(dāng)然圖論不僅僅是要描述對象之間關(guān)系，還要研究特定關(guān)系之間的內(nèi)在規(guī)律，一般情況下圖中點的相對位置如何、點與點之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系并不是重要的，如對趙等七人的相互認識關(guān)系我們也可以表示如下，可見圖論中的圖與幾何圖、工程圖是不一樣的。 1 圖與網(wǎng)絡(luò)的基本概念 a1 a2 a3 a4 a14 a7 a8 a9 a6 a5 a10 a12 a11 a13 a15 (v1) 趙 (v2)錢 (v3)孫 (v4)李 (v5) 周 (v6)吳 (v7)陳 如果我們把上面例子中的“相互認識”關(guān)系改為“認識” 的關(guān)系，那么只用兩點之間的聯(lián)線就很難刻畫他們之間的關(guān)系了，這時我們引入一個帶箭頭的聯(lián)線，稱為弧。相互認識用兩條反向的弧表示。 1 圖與網(wǎng)絡(luò)的基本概念 ? 無向圖： 由點和邊構(gòu)成的圖，記作 G=（ V， E）。 ? 連通圖 ： 對無向圖 G，若任何兩個不同的點之間，至少存在一條鏈，則 G為連通圖。 ? 賦權(quán)圖： 對一個無向圖 G的每一條邊 (vi,vj)，相應(yīng)地有一個數(shù) wij，則稱圖 G為賦權(quán)圖， wij稱為邊 (vi,vj)上的權(quán)。 管 理 運 籌 學(xué) 26 167。這條路上所有弧的權(quán)數(shù)的總和被稱為從 Vs到 Vt的距離。如果 vt已標(biāo)號（ lt,kt），則 vs到 vt的距離為 lt，而從 vs到 vt的最短路徑，則可以從 kt 反向追蹤到起點vs 而得到。如果上述的弧的集合不是空集，則轉(zhuǎn)下一步。在所有的 sij中，找到其值為最小的弧。 { ( , ) | , }i j i jv v v I v J??管 理 運 籌 學(xué) 最短路問題是網(wǎng)絡(luò)分析中的一個基本問題，它不僅可以直接應(yīng)用于于解決生產(chǎn)實際的許多問題，若管道鋪設(shè)、線路安排、廠區(qū)布局等，而且經(jīng)常被作為一個基本工具，用于解決其它的優(yōu)化問題 . 定義 給定一個賦權(quán)有向圖 D = (V,A)，記 D中每一條弧 上的權(quán)為為 。 ija ?? ?)(sv tvsv tv)(P? ???PvvijjiP),()( ??sv tv)(m i n*)( PP ?? ?tvsv管 理 運 籌 學(xué) 28 最短路問題 網(wǎng)絡(luò)： 規(guī)定起點、中間點和終點的賦權(quán)圖； 有向網(wǎng)絡(luò)： 網(wǎng)絡(luò)中每個邊都是有向邊； 無向網(wǎng)絡(luò)： 網(wǎng)絡(luò)中每個邊都是無向邊； 混合網(wǎng)絡(luò)： 網(wǎng)絡(luò)中既有有向邊，又有無向邊； 網(wǎng)絡(luò)最短路線問題： 尋找網(wǎng)絡(luò)中從起點 v1 到終點 vn 的最短路線。 管 理 運 籌 學(xué) 29 ? 結(jié)合例題學(xué)習(xí)、掌握求最短路的狄克斯拉、海斯和福德三個方法： 狄克斯拉方法：適用于滿足所有權(quán)系數(shù)大于等于 0（ lij≥0）的網(wǎng)絡(luò)最短路問題，能求出起點 v1 到所有其它點 vj 的最短距離； 海斯方法：基本思想是在最短路線上任意兩點間路線也是最短路線。 管 理 運 籌 學(xué) 30 167。 標(biāo)注 vk(lk， k1) 定義： k=1時， l1=0， k1=s， v1(0， s） min(? lij ) Min L(?) = ? lij ?為從 v1 到 vn 的通路； lij?? 其中， lij為從 vi 到 vj 的一步距離。 2 最短路問題 例 2 電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。 解：這是一個求無向圖的最短路的問題。也可直接在無向圖中用 Dijkstra算法來求解。 V1 （甲地） 15 17 6 2 4 4 3 10 6 5 v2 V7 （乙地） v3 v4 v5 v6 管 理 運 籌 學(xué) 33 167。試確定一個 5年計劃，使總支出最小。 項目 第 1年 第 2年 第 3年 第 4年 第 5年 購買費 11 11 12 12 13 機器役齡 01 12 23 34 45 維修費 5 6 8 11 18 殘值 4 3 2 1 0 解： 把這個問題化為最短路問題。 2 最短路問題