现代物流管理(第二版)-单个起点单个终点的最短路径计划.pdfVIP

单个起点单个终点的最短路径计划

已知一个由节点V｛V，V，...V｝和边E｛e,…e｝组成的网络，每条边代

oinm

表了两个节点直接相连，并且已知它们之间的长度——运输成本。要寻找从一个

节点到另一个节点之间总长度最短的路径。

假设要求从V到V的最短路径，已知

0n

|e|,e（V,V）E

ij

c0,ij

ij

,其他

一个简单的办法是根据以下原理来设计的。

原理：如果｛V,V,...V｝是V到V的最短路径，则｛V,V,...V｝也是V到V的

oikokoik10k1

最短路径。

方法是个迭代过程，希望至少能在第k步找出第k个离起点最近的节点，这样

最多n步就可以得到V到V的最短路径了。

on

在第k步开始时，我们有一些“已解节点”（即已经算得V到它的最短路径,

o

第1步时仅有V），对于要求的节点，其最短路径可以从所有的已知最短路径上加

o

一个节点所形成的路径中去求。

这样，我们就可以得到一个标号的过程来求起点到任何节点的最短路径。以

l表示从V到V的最短距离。

jij

第1步，从V出发，找出与V相邻节点V中距离c最小的一个，将其标号

oor0r

（V,C）*，每个标号点的标号包含两部分：前者表明它的标号是从哪一点而来的，

oor

后者表示从起点到该点的总距离。

第2步，从已标号节点（已解节点）出发，找出与已标号节点紧邻的所有未解

节点，若lmin（lC），则将V标号，V成为已解节点。

oqorrqqq

r,q

第3步，重复第2步，直到V成为已解节点

n

在实际的标号过程中，可以对每个新的已解节点V，将所有与其相邻的未解节

j

点V，在图上标号(V,?lC)，再在所有未标定的标号中路径最短的标号标定，

kjk0jjk

即成为这样一个过程：

第1步，对每个与V直接相连的节点V，标号(V.C