湖南大學(xué)離散數(shù)學(xué)教案--圖論.ppt

第五章圖論 楊圣洪 5 1圖的概念與描述 由結(jié)點(diǎn)和連結(jié)兩個(gè)結(jié)點(diǎn)的連線所組成的對(duì)象稱為 圖 至于結(jié)點(diǎn)的位置及連線的長(zhǎng)度無緊要 形式定義 三元組 V G E G M E V 稱為圖 其中V G 為點(diǎn)的集合 非空集 E G 是邊集 M E V 邊與點(diǎn)連接關(guān)系 常簡(jiǎn)化為二元組 V G E G 稱為圖 簡(jiǎn)記為G V E 5 1圖的概念與描述 鄰接矩陣 對(duì)于有向圖 如果從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj之間有一條邊 則a i j 1 否則為0 由于結(jié)點(diǎn)vi到vj有一條邊 反過來vj到vi之間不一定有一條 故不一定對(duì)稱 對(duì)于無向圖 如果結(jié)點(diǎn)vi到Vj有一條邊 則a i j 1 否則為0 由于Vi到Vj有一條邊時(shí) 反過來Vj到Vi肯定也有一條邊 故它是對(duì)稱的 可表示自環(huán) 不能表示重邊 5 1圖的概念與描述 關(guān)聯(lián)矩陣 關(guān)聯(lián)矩陣表示結(jié)點(diǎn)與邊之間的關(guān)聯(lián)關(guān)系 對(duì)于有向圖 如果Vi是ej的起點(diǎn) 則b i j 1 如果Vi是ej的終點(diǎn) 則b i j 1 如果以上兩種情況不存在 則b i j 0 對(duì)于無向圖 如果Vi到ej某個(gè)端點(diǎn) 則b i j 1 否則b i j 0 該矩陣的行對(duì)應(yīng)為 點(diǎn) 列對(duì)應(yīng) 邊 n m ej Vi ej Vi ej Vi ej Vi 重邊可表示 自環(huán)不可能表示 A B C D e1 e2 e3 e4 e5 e6 e7 a b c d e1 e2 e3 e4 e5 e6 V a b c d E e1 e2 e3 e4 e5 e6 V 稱為結(jié)點(diǎn)數(shù) 記為n該值有限 有限圖 E 稱為邊數(shù) 記為m 該值有限 有限圖無限圖 如果每條邊都有方向的 則為有向圖 如果每條邊都沒有方向 則為無向圖 某些邊有方向 某些邊沒有方向 混合圖 有向圖無向圖 鄰接 有向邊e1 A與D相鄰 e1與A D相關(guān)聯(lián) 稱A為D的直接前趨 D為A的后繼 點(diǎn)與點(diǎn)相鄰 點(diǎn)與邊關(guān)聯(lián)無向邊e1 a b a與b相鄰 e1與a b相關(guān)聯(lián) 只與一個(gè)結(jié)點(diǎn)關(guān)聯(lián)的自環(huán) 自旋 某兩個(gè)點(diǎn)之間有多條邊為重邊 多重圖 無環(huán)無重邊簡(jiǎn)單圖 度 某結(jié)點(diǎn)關(guān)聯(lián)邊的條數(shù) 稱為該點(diǎn)的度數(shù) D A 5 d入 A 1 d出 A 4 有向圖d入 A d出 A d A 5 入 進(jìn)入某結(jié)點(diǎn)的邊 也稱為 負(fù)邊 負(fù)度 出 離開某結(jié)點(diǎn)的邊 也稱為 正邊 正度 各點(diǎn)度數(shù)和 邊數(shù)的2倍 deg v 2 E 2m 為偶數(shù) 證明 先去掉所有的邊 每個(gè)點(diǎn) 整個(gè)圖的度數(shù)為0增加一條邊e u v 使結(jié)點(diǎn)u與v的度數(shù)的各增加1 每增加一條邊使整個(gè)圖的度數(shù)增加2 deg v 2 E 2m 為偶數(shù) 握手定理 左圖 3 2 3 2 10 邊數(shù) 5 度數(shù)和10 邊數(shù)的2倍 2 5 右圖 3 3 3 3 12 邊數(shù) 6度數(shù)和12 邊數(shù)2倍 2 6 圖中度數(shù)為奇的結(jié)點(diǎn)有偶數(shù)個(gè) 用Vo表示度數(shù)為奇 odd 的結(jié)點(diǎn)集合 Ve為偶 even 的結(jié)點(diǎn)的集合 則有 edeg v odeg v deg v 2m 因Ve中每點(diǎn)度數(shù)均為偶數(shù) edeg v 為偶數(shù) 不妨記為2k odeg v 2m 2k 2 m k 由于Vo中每個(gè)結(jié)點(diǎn)的度數(shù)為奇數(shù) 不妨依次記為2n1 1 2n2 1 2nt 1 t為個(gè)數(shù) 其和為2 n1 n2 nt 1 1 1 2n t 2n t 2 m k 個(gè)數(shù)t 2 m k 2n 2 m k n 左圖度數(shù)為奇的點(diǎn)有 A 5 B 3 共2個(gè)右圖度數(shù)為奇的點(diǎn)有 B 3 D 3 共2個(gè) 有向圖中出度 正度 和 入度 負(fù)度 和 在有向圖中 每條邊都有起點(diǎn) 與終點(diǎn) 每加一條邊使起點(diǎn)的出度增加1 整圖的出度增加1 每加一條邊使終點(diǎn)的入度增加1 整圖的入度增加1 每邊使整圖的出度 入度各增加1 所有的邊加起來 增加的出度和 入度和 正度 出度 4 1 1 2 8負(fù)度 入度 1 2 3 2 8正度和 負(fù)度和 n個(gè)結(jié)點(diǎn)完全圖Kn的邊數(shù) n n 1 2 Kn n個(gè)結(jié)點(diǎn)的完全圖 該圖的任何兩個(gè)結(jié)點(diǎn)之間都有邊相連 每個(gè)點(diǎn)都與其它n 1個(gè)點(diǎn)之間有邊相連 每個(gè)點(diǎn)度數(shù)為 n 1 n個(gè)點(diǎn)的度數(shù)和n n 1 而整圖的度數(shù)和為n n 1 邊數(shù)2倍 2m n n 1 2m 故邊數(shù)m n n 1 2由組合學(xué)可知m C n 2 證明了c n 2 n n 1 2說明 簡(jiǎn)單圖中點(diǎn)的度 n 1 邊數(shù) n n 1 2 邊數(shù) n n 1 2 非空簡(jiǎn)單圖一定存在度相同的結(jié)點(diǎn) 證明 圖G的結(jié)點(diǎn)數(shù)記為n 由于它是簡(jiǎn)單圖 無重復(fù)邊與自環(huán) 每點(diǎn)的度數(shù)取值范圍是0 n 1 當(dāng)沒有度數(shù)為0的結(jié)點(diǎn)時(shí) 每點(diǎn)度數(shù)的取值范圍是1 n 1 根據(jù)鴿巢原則 這n個(gè)點(diǎn)中至少有2個(gè)點(diǎn)的度數(shù)相同 當(dāng)有度數(shù)為0的結(jié)點(diǎn)時(shí) 剔除所有度數(shù)為0的結(jié)點(diǎn) 對(duì)剩下來的結(jié)點(diǎn)所組成的圖使用前面的證明 3 2 2 33 3 3 3 例題某班有23人 班長(zhǎng)說每個(gè)人恰好只與其他7個(gè)人關(guān)系密切 請(qǐng)問班長(zhǎng)的話可信嗎 解 將以上問題用圖表示 23個(gè)人則23個(gè)點(diǎn)表示 i號(hào)同學(xué)對(duì)應(yīng)結(jié)點(diǎn)i 如果某兩位同學(xué)關(guān)系密切 則對(duì)應(yīng)的結(jié)點(diǎn)間用一條邊相連 說每個(gè)人恰好只與其他7個(gè)人 說明與每位同學(xué)相連的邊數(shù)為7 即其度數(shù)為7 23位同學(xué)的度數(shù)和 23 7 161 由握手定理有161 2m 一個(gè)奇數(shù)不可能等于一個(gè)偶數(shù) 顯然矛盾 故班長(zhǎng)的話不可信 用圖論來解決問題 關(guān)鍵是將問題中的對(duì)象表示為結(jié)點(diǎn)或邊 5 2圖的連通性 定義一個(gè)有向圖中 從任意結(jié)點(diǎn)出發(fā) 若沿著邊的箭頭所指方向 連續(xù)不斷向前走 能到達(dá)所有的結(jié)點(diǎn) 則此圖連通 否 是 5 2圖的連通性 定義一個(gè)無向圖中 從任意結(jié)點(diǎn)出發(fā) 沿著邊連續(xù)不斷向前走 能到達(dá)所有的結(jié)點(diǎn) 則此圖是連通的 是 5 2圖的連通性 看圖判斷連通性 僅對(duì)結(jié)點(diǎn)數(shù)比較少的圖可行 結(jié)點(diǎn)數(shù)較多時(shí)需要尋求更高效的方法 前面求傳遞閉包時(shí) 如果某兩個(gè)結(jié)點(diǎn)之間通過傳遞可達(dá) 則在這兩點(diǎn)之間加上一條邊 稱為復(fù)合邊 因此求完傳遞閉包后 如果某二個(gè)點(diǎn)之間有邊相連 則表明這二個(gè)結(jié)點(diǎn) 要么未求閉包之前是直接相連的 要么這兩個(gè)點(diǎn)之前不是直接連接 是通過傳遞可達(dá) 圖與其鄰接矩陣 相當(dāng)于關(guān)系圖與其關(guān)系矩陣 因此求傳遞閉包的方法可用來判斷圖的連通性 即WarShall算法 鄰接矩陣的邏輯冪次方運(yùn)算 例題判斷下圖是是否連通 a 1 3 0從結(jié)點(diǎn)1不能走到結(jié)點(diǎn)3 看圖可知 其他0類似a 1 5 1從結(jié)點(diǎn)1出發(fā)可達(dá)結(jié)點(diǎn)5 看圖可知 其他1類似 例題若求跨越1條邊 2條邊 n 1條邊的路 究竟有多少條 則直接計(jì)算鄰接矩陣的冪次方A A2 A3 An 1 5 3Euler問題 七橋問題 每橋僅走一次 回到家里 定義5 3 1如果從某點(diǎn)出發(fā) 沿著邊不斷前行又回到起點(diǎn) 那么稱沿途經(jīng)過的邊構(gòu)成一個(gè)回路 如下圖中 a b d是一個(gè)回路 a b a是一個(gè)回路 a b d c a也是回路 定義5 3 2如果從某點(diǎn)出發(fā) 沿著邊不斷前行能走遍所有的邊 但不回到起點(diǎn)則稱為歐拉路 定義5 3 3如果從某點(diǎn)出發(fā) 沿著邊不斷前行能走遍所有的邊 并且回到起點(diǎn)則稱為歐拉回路 存在歐拉回路的圖也稱為歐拉圖 定理5 3 1無向圖G有歐拉回路 所有結(jié)點(diǎn)度數(shù)為偶數(shù) 定理5 3 2無向圖G有歐拉路 所有結(jié)點(diǎn)度數(shù)為偶數(shù) 或者只有2個(gè)結(jié)點(diǎn)度數(shù)為奇數(shù) 左圖中度數(shù)為 deg a 5 deg b 3 deg c 3 deg d 3 故沒有歐拉回路 故七橋問題無解 中圖 deg a deg d 3 有歐拉路沒無回路右圖 deg 1 2deg 2 4deg 3 4deg 4 2deg 5 2故有歐拉回路 為歐拉圖 判斷下面圖能否可以一筆畫出 5 4哈密爾頓圖 1859年 英國(guó)數(shù)學(xué)家哈密頓 用一個(gè)規(guī)則的實(shí)心十二面體 標(biāo)出世界著名的20個(gè)城市 5 4哈密爾頓圖this 定義5 4 1如果圖中存在一條 經(jīng)過所有結(jié)點(diǎn)一次也僅一次的路 則稱為哈密爾頓路 如果回到起點(diǎn)稱為哈密爾頓回路 存在哈密爾頓回路的圖稱為哈密爾頓圖 定義5 4 2如果圖中沒有一個(gè)結(jié)點(diǎn)上有自旋 任意二個(gè)結(jié)點(diǎn)間最多一條邊 則稱為簡(jiǎn)單圖 定理5 4 1設(shè)G是具有n結(jié)點(diǎn)的簡(jiǎn)單圖 如果G中每一對(duì)結(jié)點(diǎn)度數(shù)和 n 1 則G中存在一條哈密爾頓路 即存在一條經(jīng)過所有點(diǎn)一次的路 定理5 4 2設(shè)G是具有n結(jié)點(diǎn)的簡(jiǎn)單圖 如果G中每一對(duì)結(jié)點(diǎn)度數(shù)和 n 則G中存在一條哈密爾頓回路 即存在一條經(jīng)過所有點(diǎn)一次的回路 充分而不必要 5 4哈密爾頓圖 左n 5 任意2點(diǎn)和 4有H路 右n 6 任意2點(diǎn)和 5有H路下圖n 6 任意2點(diǎn)和 4 5 不滿足條件但有回路 充分條件 滿足肯定是 不必要 是不一定滿足 5 4哈密爾頓圖 定理5 4 3若圖G 具有哈密爾頓回路 則對(duì)于結(jié)點(diǎn)集V的每個(gè)非空子集S 均有W G S S 當(dāng)取S 1 5 時(shí)上圖變成了下圖被分成了3塊 即W G S 3 而 S 2 故不滿足W G S S 故不是H圖 5 4哈密爾頓圖 去掉1個(gè)結(jié)點(diǎn)后W G S 1 S 去掉2個(gè)結(jié)點(diǎn)后W G S 1 S 去掉3個(gè)結(jié)點(diǎn)后W G S 1 S 去掉4個(gè)結(jié)點(diǎn)后W G S 1 S 去掉5個(gè)結(jié)點(diǎn)后即W G S 1 S 去掉6個(gè)結(jié)點(diǎn)后W G S 4 S 均滿足但不是H圖 可用AB標(biāo)記法檢測(cè) 必要不充分 5 4哈密爾頓圖 如果有多條哈密爾頓回路 距離都已標(biāo)在每條邊上 哪條路最短呢 稱為 旅行商問題TSP TravelingSalesmanProblem 或貨郎擔(dān)問題 如 1 2 3 4 5 1 路長(zhǎng)為4 16 11 13 10 54但是1 2 4 3 5 1 路長(zhǎng)為4 3 11 4 10 31 只能一一試探 其計(jì)算量相當(dāng)大 是一個(gè)不可能在多項(xiàng)時(shí)間內(nèi)解決的問題 稱為NP NonPolynomial 難問題 5 5平面圖與染色問題 定義5 5 1如果一個(gè)簡(jiǎn)單圖中任意兩條邊不在中間相交 僅在兩個(gè)端點(diǎn)相交 或?qū)⒛承┻吚L(zhǎng)或縮短后 也可做到不在中間相交 也稱為平面圖 或可平面化的圖 一律稱為 平面圖 5 5平面圖與染色問題 定義5 5 2平面圖中由邊圍成的封閉區(qū)域稱為為面或域 如下圖中 有1 3 4 1圍成的面1 1 2 4 1圍成的面2 2 4 3 2圍成的面3 還有1 3 2 1之外的廣闊的外圍空間也是一個(gè)面 所以該圖共有4面 定理5 5 1平面圖中面數(shù) 邊數(shù) 點(diǎn)數(shù) 2 如下圖中 面數(shù)d 4 邊數(shù)m 6 點(diǎn)數(shù)n 4 顯然有d m n 2 5 5平面圖與染色問題 定義5 5 3在點(diǎn)數(shù)大于3的平面圖中 如果在不相鄰的兩個(gè)點(diǎn)之間添上一條邊 新添邊肯定與其他邊相交 即變成非平面圖 則該圖為極大可平面圖 如果所有點(diǎn)相鄰 這種圖稱為完全圖 不可能再加邊了 肯定為極大可平面圖 如下圖每個(gè)面的邊數(shù)為3 定理5 5 2極大平面圖中 3d 2m m 3n 6 d 2n 4 5 5平面圖與染色問題 證明 極大平面圖中任何面的邊只有3條 若超過3條如達(dá)4條則至少為四邊形 還可添加邊這與極大平圖矛盾 每條邊均是面的邊界線 是兩個(gè)面的邊界 故數(shù)各個(gè)面的邊界數(shù)時(shí) 每邊被數(shù)了2次 所有面的邊界數(shù)和 2m 極大平面圖中每個(gè)面只有3條邊 d個(gè)面共有3d條邊 所以3d 2m 將d m n 2代入有 3 m n 2 2m 故m 3n 6 將m 3d 2代入d m n 2中 d 3d 2 n 2 故d 2n 4 5 5平面圖與染色問題 定理5 5 3平面圖中m 3n 6 d 2n 4m C 5 2 10 點(diǎn)數(shù)n 5 3n 6 9 違反了m 3n 6m C 6 2 15 點(diǎn)數(shù)n 6 3n 6 12 違反了m 3n 6 5 5平面圖與染色問題 對(duì)偶圖在平面圖每個(gè)面中取一個(gè)代表點(diǎn) 原來相鄰的兩個(gè)面的代表點(diǎn)之間用線相連 得到的圖稱為對(duì)偶圖 對(duì)原圖面的著色問題轉(zhuǎn)換為對(duì)偶圖的點(diǎn)的著色四色猜想變成 對(duì)平面圖的對(duì)偶圖的結(jié)點(diǎn)進(jìn)行著色時(shí) 最多4種顏色 可保證相鄰兩個(gè)結(jié)點(diǎn)的顏色不一樣 如果不是平面圖的對(duì)偶圖可能不止四種顏色 5 5平面圖與染色問題 Powell著色算法 1 結(jié)點(diǎn)按度數(shù)的遞減順序排階列 2 用第1種顏色對(duì)第1個(gè)結(jié)點(diǎn)著色 并且按排列次序 對(duì)與前面已著色點(diǎn)不相鄰的每個(gè)點(diǎn)著相同的顏色 3 用第二種顏色對(duì)尚未著色的點(diǎn)重復(fù) 2 步 用第三種顏色對(duì)尚未著色的點(diǎn)繼續(xù)這種過程 直到所有點(diǎn)著色 5 5平面圖與染色問題 有6貨物需要堆放 兩種貨物之間若不能放在同一個(gè)倉(cāng)庫(kù) 則用一條線相連 其相互關(guān)系如下圖所示 請(qǐng)問共需要幾個(gè)倉(cāng)庫(kù) 1 排序 B 4 D 4 A 3 C 3 E 3 F 3 2 用紅色著B 與B不相鄰的點(diǎn)是A 故A著成紅色 3 用蘭色著D 與D不相鄰的點(diǎn)是F 故F也著成蘭色用黑色著C 與C不相鄰的點(diǎn)是E 故E著成黑色 5 6樹 定義5 6 1沒有回路的連通圖 則稱為一棵樹 右圖是一棵樹 它將左圖中很多邊去掉了 回路都不見了 但是各個(gè)點(diǎn)仍是連通的 5 6樹 定義5 6 2如果一個(gè)棵樹包含某個(gè)圖的所有結(jié)點(diǎn) 則稱為該圖的生成樹或支撐樹 不唯一如右圖包括左圖的所有結(jié)點(diǎn) 故是左圖生成樹定理5 6 1樹所包含的邊數(shù)等于點(diǎn)數(shù)減1 5 6樹 定義5 6 3在賦權(quán)圖的所有生成樹中 邊權(quán)和最小的生成樹稱為最小生成樹 如圖5 20 a 的生成樹可為5 20 b 5 20 c 誰最小 5 6樹 Kruskal最小生成樹 1 選取權(quán)最小的邊e1 置邊數(shù)i 1 2 i n 1時(shí)結(jié)束 否則轉(zhuǎn) 3 3 設(shè)已選取邊為e1 e2 ei 在G中選取不同e1 e2 ei的邊ei 1 使 e1 e2 ei ei 1 中無回路 且ei 1是滿足此條件的最小邊 4 i i 1例題對(duì)于圖5 20 a 中 1 選長(zhǎng)為2的 2 5 3 4 此時(shí)i 2 2 選長(zhǎng)為3的 2 4 4 5 不能再選了 因與 2 5 2 4 成回路 i 3 3 選擇長(zhǎng)為4的 1 2 這時(shí)i 4 5 6樹 Prim最小生成樹 1 任選一結(jié)點(diǎn)V0構(gòu)成集合U 2 從U中選到V U 余點(diǎn) 最短邊 v r 入樹T v U r V U 3 U U r 4 如果 U V 回到 2 如 1 U 1 T 2 T 1 2 U 1 2 3 T 1 2 2 5 U 1 2 5 4 T 1 2 2 5 2 4 U 1 2 5 4 5 T 1 2 2 5 2 4 3 4 U 1 2 5 4 3 5 6樹 根樹 有向圖的生成樹中 如圖5 21 a 從結(jié)點(diǎn)A出發(fā) 沿著各邊箭頭所指方向前行 分多路可走遍圖中所有的點(diǎn) 如圖 b 其中A C B E F A D 這種生成樹稱為根樹 起點(diǎn)A稱為樹根 入度為0 對(duì)于入度為1出度為0的點(diǎn)為葉子結(jié)點(diǎn) 入度為1且出度至少為1的結(jié)點(diǎn)稱為內(nèi)點(diǎn)內(nèi)點(diǎn)與根結(jié)點(diǎn)一塊統(tǒng)稱為分支點(diǎn) 從根結(jié)點(diǎn)到各點(diǎn)所包含的邊之條數(shù) 稱為根結(jié)點(diǎn)到該點(diǎn)的距離 A到D C的為1 A到B為2 A到E為3 A到F離為4 距離中最大值稱為樹高或?qū)訑?shù) 5 6樹 根樹 如果結(jié)點(diǎn)至多有2個(gè)后代 稱為2叉樹 如果正好都只有2個(gè)后代 則稱為完全二叉樹 畫根樹時(shí) 如圖5 21 b 習(xí)慣將根結(jié)點(diǎn)畫在最高處所有邊都指向遠(yuǎn)離根結(jié)點(diǎn)方向 即整體朝下 對(duì)根樹的畫法適當(dāng)簡(jiǎn)化 即去掉所有邊的箭頭 如圖5 21 b 所示的根樹可簡(jiǎn)化為圖5 22所示 5 6樹 根樹 定義5 6 4設(shè)根樹T有t片樹葉v1 v2 vt 給每片樹葉賦一個(gè)權(quán)值w1 w2 wt 則稱為T的賦權(quán)二叉樹 其中l(wèi) vi 為葉子結(jié)點(diǎn)vi的長(zhǎng)度 如果存在一種賦權(quán)方式 使得值 w i l vi 達(dá)到最小 則稱為棵樹為最優(yōu)二叉樹 或稱Huffman樹 Huffman樹的構(gòu)造算法 1 對(duì)所有權(quán)值從低到高排隊(duì) 2 找出兩個(gè)最小的權(quán)值 記為W1和W2 3 用W1 W2代替W1與W2 產(chǎn)生新的隊(duì)列 4 若隊(duì)列中的點(diǎn)數(shù)大于1 則回到 1 否則轉(zhuǎn) 5 5 逆序?qū)⒁陨辖M合過程畫出來便得到Huffman樹 5 6樹 根樹 例題漢字 一地在要工上是中國(guó)同和的有 出現(xiàn)頻率依次為 2 3 5 7 11 13 17 19 23 29 31 37 41 對(duì)漢字編譯 譯出 1000101110100101111 對(duì)應(yīng)的漢字 5 6樹 根樹 原則 左小右大 組合優(yōu)先 左0右1 不足補(bǔ)0一1010111 地1010110 在101010 要10100 工0100 上0101 是1011 中1110 國(guó)1111 同011 和100 的110 有00 5 6樹 根樹 原則 左小右大 組合優(yōu)先 左0右1 不足補(bǔ)01000101110100101111 每次從根結(jié)點(diǎn)開始 100 和 0101 上 110 的 100 和 1011 是 110 不足補(bǔ)0 湊成110 譯為 的 此處右邊5下方的2 3應(yīng)畫在左邊 它違反了組合優(yōu)先 5 7最短路徑 問題 二點(diǎn)之間數(shù)據(jù)路徑最短 如圖5 24中 求結(jié)點(diǎn)1到其他各點(diǎn)的最短距離 再求2到其他各點(diǎn)的距離 Dijkstra算法如下 1 初始化 D 1 0 若1結(jié)點(diǎn)i有邊直接相連則D i 邊權(quán)W 1 i 否則D i S 1 2 若 S 則結(jié)束 否則 S中尋找D值最小的點(diǎn)i S S i 轉(zhuǎn) 3 3 在 S尋找i的后代j 若d i w i j d j 則置d j d i w i j 回到 2 5 7最短路徑 1 初始化 D 1 0 D 2 7 D 3 1 S 1 S 2 3 4 5 6 2 距離最小者i 3 S 1 3 S 2 4 5 6 3 因d 3 w 3 2 6 d 2 故d 2 6 因d 3 w 3 5 3 則d 5 3 因d 3 w 3 6 8 則d 6 8 回到 2 2 距離最小者i 5 S 1 3 5 S 2 4 6 3 因?yàn)閐 5 w 5 4 8 則d 4 8 回到 2 2 距離最小者i 2 S 1 3 5 2 S 4 6 3 因?yàn)閐 2 w 2 6 7 8 則d 6 7 回到 2 2 距離最小者i 6 S 1 3 5 2 6 S 4 3 由于結(jié)點(diǎn)4不是結(jié)點(diǎn)6后代 故迭代結(jié)束 D 1 0 D 3 1 D 5 3 D 2 6 D 6 7 D 4 8 5 7最短路徑 動(dòng)態(tài)規(guī)劃算法 適用于分段明顯 層次分明