【天津大學】《運籌學》（精品課） P32 - 32. 最短路問題 教學錄像（1）

同學們好 這節課開始我們來學習網絡分析的最短路問題 最短路問題也是運籌學非常重要的一個問題 它在實際中有非常重要的應用 下面我們先一起來看一下對問題的描述 最短路問題 求網絡中起點到其他點之間的一條最短路線 爲了更進一步說明這個問題 下面我們一塊給出了一個引力 好 這是一個有向的網絡圖 請同學們注意看一下 這個網絡圖一共有9個節點 問題是要求一下從起點V1到終點V9的一條最短路線 那麼同學們可以觀察一下 在這個有向網絡圖裏 從起點到終點可能有多條路線 比如說從V1到V2到V5直接到V9 這是一條路線 再比如說從V1到V4到V6到V7到V9 還有一些V1到V3到V2到V5到V9等等有多條路線 那麼每一條路線都有自己的長度 所以這條路線的長度也就是說這條路線上各條邊的全數之和 比如說從V1到V2到V5到達V9 那麼這條路線中它的長度應該是多少呢 6加1加6 是13 那麼每一條路線都有自己的長度 所有這些路線中哪一條路線是最短的呢 那麼最短路問題就是來尋找這樣一條最短的路線 那麼可能同學們也想到了 那麼最短路問題還不簡單嗎 直接把所有的從起點到終點的路線給找出來 然後分別求一下各條路線的自己的長度 最終再來比一比 看看哪條長度最短 那不就是最短路線了嗎 當然了這也是一種想法 但是這種想法顯然在實際操作的時候會遇到一些問題 比如說有可能我們在尋找從起點到終點的這些路線中 在尋找的過程中可能會落下那麼一兩條 這樣的話可能直接會影響到最終求解的結論的正確性 再一個這種方法我們把所有的路線每舉出來 也不便於用計算機的方法來實現 那麼我們想看看有沒有一種方法 既能夠準確地求解出我們所要找的最短路線及其長度 又能夠非常的便於用計算機實現 爲什麼便於計算機實現呢 由於這是因爲對一些大型的複雜的網絡圖 如果能夠用程序來實現這樣的算法的話 可能使得它的實用性就更加增強了 好 那麼這一節課我們主要來介紹這樣一種求解算法 叫迪克斯特拉標號法 那麼迪克斯特拉標號法它的提出到現在有50多年的時間了 到目前爲止這種方法仍然是非常有效的方法之一 也是非常著名的一種求解對等路的算法 那麼這種方法也是我們這一節重點介紹的方法 好 那麼接下來我們先對這個算法它的基本思想進行一個概述 這個算法基本思想是這麼說的 首先從起點Vs開始 逐步地給每個節點Vz標號 那麼Vz標號有兩塊內容 一個是dz再一個是Vi 那麼標的這兩部分內容 每一部分內容都有它們具體的含義 我們先來看其中這個dz表示什麼含義 是起點Vs到Vz的最短距離 也就是說這個dz是一個數 它表示的是我正在標號這個Vz節點 從起點到它最短距離是這個數 好 這是第一部分內容 第二部分內容這個標號內容是Vi Vi是一個節點 具體的來說是該最短路線上的前一個節點 那麼這兩部分內容都有這樣的具體含義 我們看最終我們都要在求解對載路線題中 都會把它們應用到最終的結論之中 首先第一個數 比如說我們從起點開始標 要求起點到最終那個點的最短距離 那麼當給終點標上這個dz以後 顯然這個終點標的這個數 就是我們最終要求的那個最短距離 而這個第二部分內容有什麼作用呢 我們將來在描述算法的時候會看到 通過第二部分這個內容 就是這個節點信息 我們可以追蹤一下 反向追蹤把這條最短路線最終給找出來 所以這兩部分內容都有它們非常重要的作用 我們在標號的時候 每一個節點要標的話 都要標上這樣相應的一些內容 好 這是一個大體的基本思想 接下來我們就來看一下具體的方法步驟 那麼我們仍然以最開始給出的這個引力爲例 求位1到位9的最短路 好 接下來我們就來具體的敘述這個算法 算法一共分爲四大步 第一步首先是給起點標號 起點位1標什麼呢 肯定的是任何網絡圖求最短路問題 起點位1標的都是0 位1 那麼這兩個數標的這兩個內容 我們按照剛纔給的這個基本思想可以理解一下 這個0是什麼含義呢 0應該是起點到正在被標號這個節點的 當前這個節點的距離 那起點到當前這個節點 當前這個節點不就是位1嗎 它的最短距離當然就是0了 然後第二部分標號內容 這個位1是什麼意思呢 我們按照剛纔基本思想 指的是當前正在標號這個節點的它的上一個節點 上一個節點是誰呢 由於位1就是一個起點 所以它的上一個節點沒有別人 只有它本身 所以那麼給起點最終標號就是0 位1 我們具體的在圖形中的位1這個節點旁邊 給它標上0 位1 好 這是第一步 那麼對於任何一個網絡圖 我們在給起點標號的時候 我都是同樣的標上0 位1 第二步 把頂點集V分成兩塊 位A和位B 其中的位A表示是以標號點集 而位B表示未標號點集 也就是說這一步的算法 我們看到並沒有做實質的標號工作 而是把整個節點集做了一個劃分 分成兩塊 位A和位B 我把它記錄爲A和位B 像有的教材上也可以把它標記爲位A和位B等等 只是不同的記號而已 那麼這兩部分一定要要求第一部分節點 就已經標完號的這樣一個節點集合 而第二部分節點應該是還剩下的 還沒有標號的 或者說將要標號的這些節點 好 這是第二步做了一個節點的劃分 接下來我們看第三步 第三步也是算法中最重要的一步 最核心的一步 我們一起來看一看這個算法的第三步 考慮所有這樣的邊 位I 位J 其中位I要求屬於位A這個集合 位J屬於位B這個集合 然後進一步的挑選其中 與起點位1 距離最短的位J 對位J進行標號 那麼距離最短的位J是哪一個呢 我們在這還給出了一個具體的公式 通過這樣一個求最小值的方法 來具體的找出這個位J來 我們看一下 是DI加上CIJ 然後求最小值 好 這個算法這一步非常的相對麻煩一些 或者說它的步驟稍微敘述的內容也更多一些 我們再從頭來理解一下這個方法 這個步驟是什麼意思 考慮所有這樣的邊 位I位J 位I屬於位A 位J屬於位B 什麼意思呢 實際上指的就是 位A不是是以標號點擊嗎 位B是還沒有標號點擊 所以這樣的邊位I位J指的就是從以標號節點指向 還沒有標號的節點所有可能的弧 我們都要考慮一下 那麼從這些弧中對應的那個 還沒有標號那些節點 其中選一個跟位E距離最近的進行下一步標號 具體的來說 挑選其中位E距離最近要這麼來算 這個DI是什麼意思呢 指的是從位I指向位J前面這條邊 其中位I不是已經標了號嗎 它所標的那個具體的數 DI 加上CIJ指的是位I位J這條邊的它的全數 可能有多條邊 那麼多條邊的話 每一個邊都會算出這樣一個數來 再來求最小值 那麼哪個邊求出的值最小 它對應的位置要進行下一步的標號 好 我們接下來結合這個例題 再來具體的來解釋一下這個步驟 到目前來說 我們一塊看一下 從以標號點擊指向未標號點擊的邊 請同學們一塊來找一下 看看有哪一些 一共應該有三條 一個是位I到位II 再一個是位I到位III 還有位I到位IV 那麼這三條邊 就是說所有這樣的標 滿足這個條件 以標號點擊指向未標號點擊的所有的標 那麼這三條邊 它們對應的末尾接點位II位III和位IV 將成爲下一步要標號的一個候選 或者說我們將要從這三個接點中 選出一個進行下一步的標號 具體怎麼選 那就看這三個接點 哪個接點和位I距離最近 那麼具體怎麼看 當然有的同學說了 我現在直接就能觀察出來 那麼位II這個接點距離位I是6 位III的接點距離位I是3 而位IV距離位I接點距離是1 最小值當然是位IV對應的這條邊了 也就是說最小值是1 所以下一步應該給位IV標號 沒錯 下一步確實是給位IV標號 那麼我們也可以用一下剛纔我們在這個步驟中 給出的公式來具體地算一下 爲什麼是給位IV標號 因爲雖然在這一步中還能夠直接觀察出來 在將來後續的標號過程中 可能沒法或者是不便於 不容易直接來觀察 那麼這時候用這樣一個公式來計算 就更加準確 更加嚴格了 我們按這個公式來算一下 dI加上cIj其中dI就是以標號的接點 已經標的這個數當然是0了 那麼cIj就是各條邊上的全數 所以應該是0加6 0加3和0加1這三個數 分別也當然也就是631了 取最小值是1 所以給位IV標下一個 那麼位IV標什麼內容呢 首先它標的第一塊內容是一個數 表示的是起點到該點的對轉距離 而這個數就是剛纔通過求最小值求出來的那個1 第二部分內容是一個節點 表示的是該節點 就是當前正在標號這個節點 它是從哪個節點指過來的 當然是從位1過來的 或者說它的上一個節點是位1 所以第二部分標號內容就是位1 最終我們給位IV標上這樣一塊內容 1位1這樣一個標號 這就是第三大步 最後一步 不斷地重複二和三這兩步驟 重複二和三直至給終點位N也標上號 位N標的號假設我們記得DNVI 那麼根據我們前面的分析 顯然這個DN就是最終我們要求的起點到終點的對轉距離 然後我們可以再進一步地 根據它這個標號的第二部分內容節點信息 從位N反向追蹤 最終找出這條對轉路線來 目前來說我們還沒有標到最後這個終點V9 所以我們先來看不斷地重複二和三 第二步 請朋友們再來回想一下 當時是怎麼着的呢 是做一個節點劃分 比如說把整個的頂點及位分成兩塊 第一部分是以標號點擊 第二部分是未標號點擊 這是第二步 第三步就是從指向位標號的所有的邊中挑選 他們這個末尾節點中跟位一距離最近的那個節點進行下一步的標號 第三步我們也說過 它是整個算法的一個最核心的步驟 那麼這一步不斷地重複二和三 就這樣不斷地重複 我們接下來以這個例題爲例來繼續地來演示這一步驟 第二步 重複第二步 那麼把頂點擊做重新的劃分 現在請朋友們看一下 以標號點擊 已經是位一和位四了 所以它倆作爲位A這個集合 它剩下這些節點都還沒有標號 是位B 然後第三步 考慮所有從以標號指向位標號的邊 我們一塊來找一下 一共有哪些邊呢 位一到位二 位一到位三 還有位四到位六 這三條邊滿足這個條件 也只有這三條邊目前來說 請朋友們一定要注意反向的不能算 像位三到位四 位五到位四這些弧 不能作爲要標號的候選的標 好 那麼這三條邊 它們的末尾節點分別是位二位三位六 這三個節點將要成爲下一步要標號的一個候選節點 我們要從中挑選出 某一個節點 看哪個節點跟位一距離最近 進行下一步的標號 那怎麼來挑選呢 我們繼續用一下剛纔的公式就可以了 位二到位一的距離 我們可以用零加六來算一下 而位三用零加三來算一下 而位六是一加上十 這樣我們又算出了三個數 分別是六三和十一 那麼顯然最小的數是 位一到位三這條邊對應的三 零加三算出來的三是最小的 所以按照算法 我們下一步就要給位三標號 標什麼呢 顯然標的數是三 而它的上一個節點 或者說位三是從哪一個節點引過來的呢 是從位一過來的 所以最終給位三標號是三位一 這樣的話我們又做了一次重複 做了一次循環 已標號節點是這樣了 要不斷的重複二和三 直至給終點 VN標號爲止 好 那麼我們繼續往後循環 已標號點擊是位一位三位四這三個節點 那麼剩下的節點都還沒有標號 我們進一步的來看一看 從已標號節點指向未標號節點的弧有哪些呢 位一到位二 位三到位二 和位四到位六 這三條弧它們對應的末尾節點位二和位六呢 將要成爲下一步要標號的候選 從中我們挑選一個和位一距離最近的來進行下一次的標號 我們來看一下位二 位二如果從位一直接指過來的話 它的距離應該是零加上六 是六 位二如果從位三來過來呢 走這條弧過來 也可以算一下 位三已經標了這個數是三 再加上這個全數二呢是五 好 我們先把這個數記住是五了 再看位六 位六要是從位四過來的話 這條邊 全數是十 然後位四已經標的數是一 這倆數加起來是十一 最終我們得到了三個數 分別是六 五和十一 最小值顯然是五 所以接下來給位二標號標的內容是五 並且是從位三指過來 得到了這個五 得到了這個剛纔算出的這個最小值 所以標號是五 位三 這樣又進行了一次循環 我們繼續下一次循環 對節點集做重新的劃分 以標號點集呢是前四個節點了 從以標號指向位標號的邊呢 我們繼續來找一下 一共有位二到位五 位四到位六 這兩條邊 然後呢我們依次來計算一下 位五從位二過來 距離是五加一是六 而位六呢是一加十還是十一 那這兩個數最小值呢顯然是六 所以下一步要給位五標號 標什麼呢 應該是五加一是六 六位二對吧 又進行了一次循環 那麼接下來以標號點集呢是 位一位二位三位四位五 這五個節點構成的集合 剩下的其他的節點呢都還沒有標號 從以標號點集位A指向位標號點集位B的弧 一共有四條 位四到位六 位五到位六 位五到位七 和位五到位九 那麼也依次來計算一下 位六如果從位五過來的話 那麼這個數是六加四是十 從位四過來的話是一加十 十一 位七呢從位五過來 數是六加三是九 位九 六加六是十二 那麼最小值呢 剛纔已經算出了四個值 分別是十十一 九十二 那麼最小值顯然是九 所以 我們下一步就要給位七標號 位七標號內容應該是 九位五 這樣又進行了一次標號 我們重新對點集做劃分 已標號節點集現在是位一位二位三位四位五和位七 這樣幾個節點構成的集合 剩下其他節點呢都還沒有標號 那麼從已標號點集指向位標號點集的弧呢 現在來看也是有四條 分別是位四到位六 位五到位六 位五到位九 和位七到位九 那麼我們也依次來算一下 位六如果從位五過來的話是十 從位四過來是十一 而位九呢 從位五過來是十二 從位七過來是十三 九加四是十三 算出了四個數分別是十十一 十二和十三 最小值顯然是十 所以 那麼我們下一步就要給位六標號 位六標的內容應該是十位五 因爲位五 到位六這條邊 它對應的那個數十是最小值的 這樣我們又進行了一次標號 那什麼時候結束呢 什麼時候我們把終點給標上號 那麼什麼時候這個算法就結束了 好現在還沒有終點標上號 所以我們繼續來進行這個算法 已標號點集現在是前七個節點 位一到位七 那麼從已標號點集指向位標號點集的弧呢 現在來看有兩條分別是位五到位九和位七到位九 我們也依次來算一下 位九如果從位五過來的話分別是六加六是十二 從位七過來是九加四十三 那麼這兩個數字最小值當然是十二了 所以最終給位九標上號 十二位五 那麼到這爲止呢 我們這個標號過程就結束了 我們最終來看一下這個結論 此時終點位九標的這個號十二位五 其中第一個數是十二 它表示什麼含義呢 就是我們要求的位一到位九的最短距離 接下來我們進一步的可以通過反向追蹤的方法 把這條最短路線具體的來找出來 我們一塊來反向追蹤一下 我們只需要把這個從位九倒轉往前追 那麼根據每一個節點標號的第二部分內容這個節點信息呢 具體的把這條最短路徑給追出來 好 我們看一下位九 位九它的上一個節點應該是位五 所以位九反向追回到位五 那麼位五的上一個節點呢是位二 所以位五反向追蹤到位二 那麼位二的上一個節點呢是位三 所以追到位三 位三的上一個節點是位一 最終到了起點 那麼我們從起點再往終點可以把這條最短路線具體的來描述出來 那也就是從位一到位三到位二到位五到位九 這就是我們最終要求的這條最短路線 最短距離呢剛纔已經求出來了是十二 好 那麼這就是這個算法結合這道例題整個的一個演示的過程 我們通過這個算法呢我們會看到它是一個不斷迭代的算法 首先給起點標號 那麼接下來給其他的節點標號 每一次在標號的時候 都是來尋找看看哪個節點跟位一當前是最近的 最近的進行標號 那麼接着繼續往後標 在沒有標號中再選最近的 直到給終點vn標上號爲止 這個標號就結束了 然後我們最後終點標的第一部分內容 那個數就是要求的最短距離 而反向追蹤可以把最短路線來具體地求出來 這就是整個算法 接下來我們請同學們一塊來看一下書上 129頁習題5.3的一個練習題 那麼請同學們可以在課堂上把這道題做一下 那麼這個問題要求求的是針對這個網絡圖 從位一到位九的最短路問題 好那麼下面我們一塊來把這個答案來公佈一下 按照算法要求呢首先給起點標號 起點標號是零位一 接下來呢 位二標號三位一 再接下來位四標號四位一 再下面是位五接點標號五位二 再下面要注意了 從以標號節點指向位標號節點 有兩條弧同時取得了最小值 比如說位二到位三 它的距離呢就是三加三是六 位二到位六呢也是六 同樣取同時取得最小值 那麼下一步具體給誰標號呢 其實我們只要從這位三和位六這兩個節點中 任選一個進行標號就行了 因爲比如說我們選選擇了位三進行了一次標號 再下一次循環的時候肯定就是另外一個 沒有標號那個同樣取得最小值那個節點要進行標號的 就最終這兩個節點實際上都會標上號 再接下來又要注意了 從以標號節點指向位標號節點呢 有兩條弧同時取得了最小值是七 分別是位六到位七和位四到位七 所以位七節點標的數呢是七 而它的上一個節點呢同時有兩個節點 位四或者位六 我們這樣來標上它 最後給位九標號 那麼最終終點位九標上號 那它標的這個數呢 8.5就是我們要求的從七點到終點的最短距離 接下來我們一塊來反向追蹤把這個最短路線來找出來 那麼位九的上一個節點是位六 位六的上一個節點是位二 位二的上一個節點是位一 好 這就是這個課堂練習題的答案 關於最短路算法呢 剛纔我們介紹這個迪克斯特拉標號算法 接下來我們有這麼幾點說明 請同學們一塊來聽一下注意一下這樣一些問題 第一 標號過程中 中間節點的那些標號內容呢也有它的明確的意義 因爲我們剛纔像包括這道習題還有前面那道例題 我們看到從七點標到終點 最終好像我們只關注了終點標的那個內容 它那個數就是最短距離 然後反向追蹤來找出最短路徑了 實際上中間節點它們那些標的那些號 是不是也有它們自己具體的內容呢 比如說我們看結合剛纔這道練習題爲例 那麼像在最短路上的這些節點 比如說位六這個節點 它標的這個六 位二是什麼意思呢 或者不在最短路上的其他的節點 它們也標了一些數 像位五標的是五位二 位七標的是七位四或者位六 那麼實際上我們看每一個節點標的這些數 比如以位七爲例吧 它標了一個七 那麼這個七顯然就是 應該是七點到位七的最短距離就是七 然後反向追蹤也可以求得位一到位七的最短路線 當然了位一到位七由於位七標了兩個節點 那麼位一到位七的最短路徑應該有兩條 這個我們在後面還會進一步說明存在多個節的問題 這是第一條說明 第二個問題要注意一下 這就是剛纔我們在還是結合這道課堂練習 我們剛纔提到的一個問題 有同樣一個最短的問題 可能會存在多條最短路徑 但是距離是唯一的 當然像這個問題 從位一到位九最短路徑那就是一個了 距離是8.5 我們剛纔說到了位七 位七這個節點它標的這個數 七是表示位一到位七的最短距離 然後我們可以反向追蹤一下 位一到位七的最短路線有兩條應該是 位七可以到達位六 到達位二 反向追蹤到位一 也就是說或者正過來讀一下 就是位一到位二到位六到位七 這是一條最短路線 也可以位七反向追蹤到位四 再到位一 那麼正過來就是位一到位四到位七 這樣一條路線也是最短路線 所以這個問題如果要求位一到位七的 最短路問題的話 存在兩個節兩條最短路線 雖然存在兩個節 那麼它的最短距離那必然是唯一的 那就是七了 其實這也是所有的最優化問題 它的一個共同的特點 那就是可能會存在多個最優節 但是最優值必然是唯一的 無論是在前幾章像線性規劃問題中 也同樣一個線性規劃問題 也可能會存在多個最優節 甚至無窮多個最優節 但是它的最優值必然是確定的是唯一的 再比如說像我們在網絡分析中 前面幾塊網絡分析內容所介紹的 有個最小支撐數問題 同樣一個最小支撐數問題 它的最小支撐數可能有多個最小支撐數 但是最小支撐數的全核 那麼它應該是唯一的 這就是所有的最優化問題共有的一個特性 可能存在多個最優節 但是最優值必然是唯一的 其實我們在後續的其他的最優化問題 比如說我們這一章網絡分析的最大流問題 還有或者網絡計劃問題 也會存在這樣的問題 存在這樣共性的一些特點 這是關於最短路算法的第二個說明 再來看第三個 當網絡中存在負的權數時 剛纔我們介紹的迪克斯特拉標號算法失效 也就是說算法求出來的結論可能是出錯的 爲此我們只需要舉一個非常簡單的例子來說明這個問題 看這樣一個網絡圖 V1 V2 V3有三個節點 那麼三條弧上它們的權數 有一個負的權數是負3 負的權數在實際的問題中它有實際的含義 比如說我們可以用正的權數表示利潤的話 那麼負的權數應該可以表示虧損 假設這樣一個實際的問題 我們又畫得了這樣一個網絡圖 要求從V1到V3的最短路 實際上這個問題我們可以直觀的非常簡單的來觀察出 從V1到V3的最短路了 顯然V1到V3只有兩條路線 一個是V1直接到V3 再一個就是V1經過V2到V3 那麼這兩條路線它的長度我們也可以分別計算一下 從上面走的話它的長度是1 而下面是2加負3是負1 顯然下面這條路線它的長度更短 或者說最短路應該是V1到V2到V3 這是它實際的最短路 那麼下面我們試着用剛纔介紹的迪克斯塔拉標號算法來求一下最短路 是不是也求出這樣的答案呢 同學們會看到實際上會求出另外一條是最短路 這樣是出錯的 我們只需要標號 首先給起點標號 起點標的是0V1 然後按照算法 從以標號指向V標號的節點 邊有兩條 一個是V1到V3 再一個是V1到V2 那麼算一算哪個數更小呢 一個0加1是1 再一個0加2是2 但是上面這個數小 所以下一次要標號就是給V3標了 標什麼呢 1V1 好了 終點已經標號了 那麼標號就結束了 按照我們前面算法 所以我們就可以根據這個算法標號這個結果來讀出最終的結論來 那麼起點到終點的最短距離應該是1 然後反向追蹤一下 最短路線應該是V1到V3 這是一個錯誤的結論 所以從這個例題我們看到 最短路算法當對於負的網絡圖的情形可能會出現一些問題 比如說算法失效 那至於負的全數問題的網絡圖如何來求最短路問題呢 實際上還有些其他的算法可以來求 比如說像弗洛伊德算法等等 這個我們在我們這門課裏邊可能就不再介紹了 同學們感興趣的話可以參考一下相關的參考教材 這是第三點要說明的 那麼最後一點補充說明 剛纔我們在前面算法描述時 包括舉這些例題都是有向的網絡圖 但是對於無向的網絡圖也有最短的問題 那是不是也可以用這個算法來求呢 答案是肯定的 也可以用狄克斯塔拉算法來求無向圖的最短的問題 我們回顧一下剛纔在狄克斯塔拉算法這個中的第三步 只需要對第三步中的 這個弧 vi到vj改爲無向邊vi vj就行了 換句話說 我們在當時第三步中是這麼說的 考慮所有從以標號節點指向未標號節點的所有的弧 就必須是在有向網絡圖裏邊 從以標號節點正向指向未標號節點的 反向指過來的不算 不能算作被考察的對象 這是有向網絡圖 而無向網絡圖每一條無向邊 如果我們把它理解爲一對雙向的有向邊這樣來理解的話 實際上無向邊就可以更簡單地來分析了 比如說每一次再來考察邊的時候 只要考慮以標號節點跟未標號節點關聯的邊 都可以作爲考察的對象 那麼它們還沒有標號的這些邊的另外一個節點 就可以作爲下一次要標號的一個候選節點 從中挑選可能起點距離最近的進行下一次標號 所以這樣做這樣一個簡單的處理 算法就同樣實用了 那麼關於無向網絡圖情形 我們也可以一塊來看一個課堂練習題 這個練習題要求求這樣一個無向網絡圖 由位一到位七的最短路 那麼接下來請同學們考慮一下 這個問題怎麼樣把我們前面介紹的 這個狄克斯塔拉算法稍微做一下改變 那麼就可以適合於求解這樣的問題了 下面我們把這個問題的答案一塊來公佈一下 這個問題我們把標號過程在這個圖形中標上了 其中要注意一下 V3節點標的這個號 它標的這個數是4 然後節點是V2或者V4 而我們這個最短路恰好又經過了V3這個節點 所以同學們應該能夠想到 這個問題它的最短路也是有兩條 最短距離當然是唯一的是13 這是第二條最短路 那麼這個在標號的時候 我們簡單的說一下 比如首先給7點位一標號 然後再接下來進行下一步標號是該給誰標的呢 那麼就要觀察一下跟位一相關聯的邊有哪些 有三條 位一到位二 位一到位三 和位一到位四 那麼下一步要給誰標呢 就是從位二位三位四中 挑選和位一最近的那個節點進行標號 那麼比如說位一到位二的距離是2 到位三是5 到位四是3 所以最近的是2 所以下一步標號就給位二標了 2位一 這是第二步標號 第三步標號一次進行下去 那麼這時候我們在每一次標號觀察的 不是像有像圖情形 從以標號節點指向位標號節點的所有的湖 而是隻要以標號節點和位標號節點關聯的邊就可以了 就做這樣一個簡單的改變 我們就可以把迪克斯塔拉標號算法推廣到無像圖情形 好了 那麼關於迪克斯塔拉標號算法 我們這節課就講到這 那麼最短路問題還有些其他的應用 我們將在下一次課中繼續來結合一些例題 來介紹最短路模型在實際問題中的應用 好 下課