（1）“纯距离”意义上的最短路径。例如，需要运送一批物资从一个城市到另一个城市，选择什么样的运输路线距离最短？（2）“经济距离”意义上的最短路径。例如，某公司在10大港口C1，C2，…，C10设有货栈，从Ci到Cj之间的直接航运价格，是由市场动态决定的。如果两个港口之间无直接通航路线，则通过第三个港口转运。那么，各个港口之间最廉价的货运线路是什么？（3）“时间”意义上的最短路径。例如，某家经营公司有一批货物急需从一个城市运往另一个城市，那么，在由公路、铁路、河流航运、航空运输等四种运输方式和各个运输线路所构成的交通网络中，究竟选择怎样的运输路线最节省时间？（二）最短路径的算法标号法的基本思想是：首先v1从开始，给每一个顶点标一个数，称为标号。这些标号，又进一步区分为T标号和P标号两种类型。其中，每一个顶点的T标号表示从起点v1到该点的最短路径长度的上界，这种标号为临时标号；P标号表示从v1到该点的最短路长度，这种标号为固定标号。在最短路径计算过程中，对于已经得到P标号的顶点，不再改变其标号；对于凡是没有标上P标号的顶点，先给它一个T标号；算法的每一步就是把顶点的T标号逐步修改，将其变为P标号。那么，最多经过k-1步，就可以求得到从起点v1到每一个顶点的最短路径及其长度。▇标号法具体计算步骤例1：在图10.2.1所示的赋权有向图中，每一个顶点vi（i=1，2，…，n）代表一个城镇；每一条边代表相应两个城镇之间的交通线，其长度用边旁的数字表示。试求城镇v1到v7之间的最短路径。解：首先给v1标上P标号P(v1)=0，表示从v1到v1的最短路径为零。其它点(v2，v3，…，v7)标上T标号T(vj)＝+∞（j＝2，3，…，7）。第一步：①v1是刚得到P标号的点。因为(v1，v2)，(v1，v3)，(v1，v4)∈E，而且v2，v3，v4是T标号，所以修改这三个点的T标号为：第二步：①v2是刚得到P标号的点。因为(v2，v3)，(v2，v6)∈E，而且v3,v6是T标号，故修改v3和v6的T标号为：第三步：①v4是刚得到P标号的点。因为(v4，v5)∈E，而且v5是T标号，故修改v5的T标号为：T(v5)＝min[T(v5)，P(v4)+w45]＝min[+∞，3+5]＝8②在所有的T标号中，T(v3)＝4最小，故令P(v3)＝4。第四步：①v3是刚得到P标号的点。因为(v3，v5)，(v3，v6)∈E，而且v5和v6为T标号，故修改v5和v6的T标号为：T(v5)＝min[T(v5)，P(v3)+w35]＝min[8，4+3]＝7T(v6)＝min[T(v6)，P(v3)+w36]＝min［9，4+5]＝9②在所有的T标号中，T(v5)＝7最小，故令P(v5)＝7。第五步：①v5是刚得到P标号的点。因为(v5，v6)，(v5，v7)∈E，而且v6和v7都是T标号，故修改它们的T标号为：T(v6)＝min[T(v6)，P(v5)+w56]＝min[9，7+1]=8T(v7)＝min[T(v7)，P(v5)+w57]＝min[+∞，7+7]=14②在所有T标号中，T(v6)＝8最小，于是令：P(v6)＝8。第六步：①v6是刚得到P标号的点。因为(v6，v7)∈E，而且v7为T标号，故修改它的T标号为：T(v7)＝min[T(v7)，P(v6)+w67]＝min[14，8+5]=13②目前只有v7是T标号，故令：P(v7)＝13。从城镇v1到v7之间的最短路径为(v1，v2，v3，v5，v6，v7)，最短路径长度为13。二、选址问题（一）中心点选址问题设G＝（V，E）是一个无向简单连通赋权图，连结两个顶点的边的权值代表它们之间的距离，对于每一个顶点vi，它与各个顶点之间的最短路径长度为di1，di2，…，din。这些距离中的最大数称为顶点vi的最大服务距离，记为e(vi)。那么，中心点选址问题，就是求网络图G的中心点，使得例2：假设某县下属的六个乡镇及其之间公路联系如图所示。每一顶点代表一个乡镇；每一条边代表连接两个各乡镇之间的公路，每一条边旁的数字代表该条公路的长度。现在要设立一个消防站，为全县的六个乡镇服务。试问该消防站应该设在哪一个乡镇（顶点）？第二步：求每一个顶点的最大服务距离。显然，它们分别是矩阵D中各行的最大值，即：e(v1)＝6，e(v2)＝7，e(v3)＝6，e(v4)＝7，e(v5)＝6，e(v6)＝7。第三步：判定。因为e(v1)＝e(v3)＝e(v5)＝min{e(vi)}＝6，所以v1，v3，v5都是中心点。也就是说，消防站设在v1，v3，v5中任何一个顶点上都是可行的。中位点选址问题的质量判据：使最佳选址位置所在的顶点到网络图中其它各个顶点的最