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

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

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

溫馨提示：

1、這種標(biāo)號(hào)算法僅適用于每條弧的長度都是非負(fù)數(shù)的情況

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

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

【試題解析】求下圖中V1到各個(gè)頂點(diǎn)的最短路徑。

【試題解析】

第1步：首先給V1標(biāo)號(hào)：V1(0，0)

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

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

第3步：到這步我們已經(jīng)得到了V1的標(biāo)號(hào)V1(0，0)，V2的標(biāo)號(hào)V2(4，1)，從已標(biāo)號(hào)的點(diǎn)到未標(biāo)號(hào)的點(diǎn)有(注意看圖中箭頭→)：

V1到V3，K13=6;

V2到V4，K24=4+5=9。(注：是V2標(biāo)號(hào)的數(shù)字“4”+V2到V4的距離)

V2到V5，K25=4+4=8

進(jìn)行比較，最小的是K13=6，所以我們給V3標(biāo)號(hào)，V3(6，1).這個(gè)(6，1)是什么意思，上面已經(jīng)說明了，就不重復(fù)了。

第4步：到這步我們已經(jīng)得到V1(0，0)，V2(4，1)，V3(6，1)，從已標(biāo)號(hào)的點(diǎn)到未標(biāo)號(hào)的點(diǎn)有(注意看圖中箭頭→)：

V2到V4，K24=4+5=9

V2到V5，K25=4+4=8

V3到V4，K34=6+4=10

V3到V5，K35=6+7=13

進(jìn)行比較，最小的是K25=8，所以我們給V5標(biāo)號(hào)，V5(8，2)

第5步：到這步我們已經(jīng)得到V1(0，0)，V2(4，1)，V3(6，1)，V5(8，2)，從已標(biāo)號(hào)的點(diǎn)到未標(biāo)號(hào)的點(diǎn)有(注意看圖中箭頭→)：

V2到V4，K24=4+5=9

V3到V4，K34=6+4=10

V5到V6，K56=8+5=13

V5到V7，K57=8+6=14

進(jìn)行比較，最小的是K24=9，所以我們給V4標(biāo)號(hào)，V4(9，2)

第6步：到這步我們已經(jīng)得到V1(0，0)，V2(4，1)，V3(6，1)，V4(9，2)，V5(8，2)，從已標(biāo)號(hào)的點(diǎn)到未標(biāo)號(hào)的點(diǎn)有(注意看圖中箭頭→)：

V4到V6：K46=9+9=18

V4到V7：K47=9+7=16

V5到V6，K56=8+5=13

V5到V7，K57=8+6=14

進(jìn)行比較，最小的是K56=13，所以我們給V6標(biāo)號(hào)，V6(13，5)

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

V4到V7：K47=9+7=16

V5到V7，K57=8+6=14

V6到V7，K67=13+5=18

V6到V8，K68=13+4=17

進(jìn)行比較，最小的是K57=14，所以我們給V7標(biāo)號(hào)，V7(14，5)

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

V6到V8，K68=13+4=17

V7到V8，K78=14+1=15

進(jìn)行比較，較小的是K78=15，所以我們給V8標(biāo)號(hào)，V8(15，7)

第9步：至此，我們已經(jīng)得到了所有點(diǎn)的標(biāo)號(hào)，也能得到V1到各個(gè)頂點(diǎn)的最短路徑

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，最短路徑怎么看呢?看括號(hào)后面的數(shù)字，數(shù)字為“2”代表V2，然后找到V2(4，1)括號(hào)后面的數(shù)字為1，代表V1，所以最短路徑V1→V2→V4

V5(8，2)，V1到V5的最短距離為8，根據(jù)上面所說的方法可以得出最短路徑為：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