关于最短路径问题，信息系统项目管理师第4版教程21.2.4动态规划中有介绍逆序法求最短路径问题，然后21.2.5图与网络介绍了标号法求最短路径问题。

对于这类问题，其实只看一些概念性的东西是很难看懂的，大家要结合试题解析、视频讲解来看。信息系统项目管理师第4版教程(628-629页)中的讲解其实是比较清楚的，大家可以仔细多看几遍，同时本文也将给大家再仔细讲解下。

官方教材上介绍了一些VS、Vt、Vj、Vn、(αj，βj)等一堆概念，初次看的话，大家肯定看的很迷糊，所以我们还是直接从试题解析入手，来解一个题，大家就了解了。

温馨提示：

1、这种标号算法仅适用于每条弧的长度都是非负数的情况

2、求解过程中如果有多于一条弧使K达到最小，也就是最小值重复的情况，可以任取其中一条

3、这种方法很繁琐，但信息系统项目管理师第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