關于最短路徑問題，信息系統(tǒng)項目管理師第4版教程21.2.4動態(tài)規(guī)劃中有介紹逆序法求最短路徑問題，然后21.2.5圖與網絡介紹了標號法求最短路徑問題。

對于這類問題，其實只看一些概念性的東西是很難看懂的，大家要結合試題解析、視頻講解來看。信息系統(tǒng)項目管理師第4版教程(628-629頁)中的講解其實是比較清楚的，大家可以仔細多看幾遍，同時本文也將給大家再仔細講解下。

官方教材上介紹了一些VS、Vt、Vj、Vn、(αj，βj)等一堆概念，初次看的話，大家肯定看的很迷糊，所以我們還是直接從試題解析入手，來解一個題，大家就了解了。

溫馨提示：

1、這種標號算法僅適用于每條弧的長度都是非負數的情況

2、求解過程中如果有多于一條弧使K達到最小，也就是最小值重復的情況，可以任取其中一條

3、這種方法很繁瑣，但信息系統(tǒng)項目管理師第4版官方教程中介紹的是這種方法，所以本文也就介紹這種方法，其他求解方法，大家可以自己去查找下相關資料。

【試題解析】求下圖中V1到各個頂點的最短路徑。

【試題解析】

第1步：首先給V1標號：V1(0，0)

第2步：看圖中的箭頭(→)，V1指向的點有兩個，分別是V1到V2，其距離我們用K12表示，V1到V3，其距離我們用K13表示。

V1到V2的距離，即K12在圖中很容易看到是4，V1到V3的距離，即K13在圖中很容易看到是6。

第3步：到這步我們已經得到了V1的標號V1(0，0)，V2的標號V2(4，1)，從已標號的點到未標號的點有(注意看圖中箭頭→)：

V1到V3，K13=6;

V2到V4，K24=4+5=9。(注：是V2標號的數字“4”+V2到V4的距離)

V2到V5，K25=4+4=8

進行比較，最小的是K13=6，所以我們給V3標號，V3(6，1).這個(6，1)是什么意思，上面已經說明了，就不重復了。

第4步：到這步我們已經得到V1(0，0)，V2(4，1)，V3(6，1)，從已標號的點到未標號的點有(注意看圖中箭頭→)：

V2到V4，K24=4+5=9

V2到V5，K25=4+4=8

V3到V4，K34=6+4=10

V3到V5，K35=6+7=13

進行比較，最小的是K25=8，所以我們給V5標號，V5(8，2)

第5步：到這步我們已經得到V1(0，0)，V2(4，1)，V3(6，1)，V5(8，2)，從已標號的點到未標號的點有(注意看圖中箭頭→)：

V2到V4，K24=4+5=9

V3到V4，K34=6+4=10

V5到V6，K56=8+5=13

V5到V7，K57=8+6=14

進行比較，最小的是K24=9，所以我們給V4標號，V4(9，2)

第6步：到這步我們已經得到V1(0，0)，V2(4，1)，V3(6，1)，V4(9，2)，V5(8，2)，從已標號的點到未標號的點有(注意看圖中箭頭→)：

V4到V6：K46=9+9=18

V4到V7：K47=9+7=16

V5到V6，K56=8+5=13

V5到V7，K57=8+6=14

進行比較，最小的是K56=13，所以我們給V6標號，V6(13，5)

第7步：到這步我們已經得到V1(0，0)，V2(4，1)，V3(6，1)，V4(9，2)，V5(8，2)，V6(13，5)，從已標號的點到未標號的點有(注意看圖中箭頭→)：

V4到V7：K47=9+7=16

V5到V7，K57=8+6=14

V6到V7，K67=13+5=18

V6到V8，K68=13+4=17

進行比較，最小的是K57=14，所以我們給V7標號，V7(14，5)

第8步：到這步我們已經得到V1(0，0)，V2(4，1)，V3(6，1)，V4(9，2)，V5(8，2)，V6(13，5)，V7(14，5)，從已標號的點到未標號的點有(注意看圖中箭頭→)：

V6到V8，K68=13+4=17

V7到V8，K78=14+1=15

進行比較，較小的是K78=15，所以我們給V8標號，V8(15，7)

第9步：至此，我們已經得到了所有點的標號，也能得到V1到各個頂點的最短路徑

V1(0，0)，

V2(4，1)，V1到V2的最短距離為4，只有一條路徑，所以最短路徑就是V1→V2

V3(6，1)，V1到V3的最短距離為6，只有一條路徑，所以最短路徑就是V1→V3

V4(9，2)，V1到V4的最短距離為9，最短路徑怎么看呢?看括號后面的數字，數字為“2”代表V2，然后找到V2(4，1)括號后面的數字為1，代表V1，所以最短路徑V1→V2→V4

V5(8，2)，V1到V5的最短距離為8，根據上面所說的方法可以得出最短路徑為：V1→V2→V5

V6(13，5)，V1到V6的最短距離為13，最短路徑為：V1→V2→V5→V6

V7(14，5)，V1到V7的最短距離為14，最短路徑為：V1→V2→V5→V7

V8(15，7)，V1到V8的最短距離為15，最短路徑為：V1→V2→V5→V7→V8