资源描述：
《单个起点单个终点的最短路径计划.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、单个起点单个终点的最短路径计划已知一个由节点和边组成的网络，每条边代表了两个节点直接相连，并且已知它们之间的长度——运输成本。要寻找从一个节点到另一个节点之间总长度最短的路径。假设要求从到的最短路径，已知一个简单的办法是根据以下原理来设计的。原理：如果是到的最短路径，则也是到的最短路径。方法是个迭代过程，希望至少能在第k步找出第k个离起点最近的节点，这样最多n步就可以得到到的最短路径了。在第k步开始时，我们有一些“已解节点”（即已经算得到它的最短路径，第1步时仅有），对于要求的节点，其最短路径可以从所有的已知最短路径上加一个节点所形成的路径中去求。这样，我们
2、就可以得到一个标号的过程来求起点到任何节点的最短路径。以表示从到的最短距离。第1步，从出发，找出与相邻节点中距离最小的一个，将其标号，每个标号点的标号包含两部分：前者表明它的标号是从哪一点而来的，后者表示从起点到该点的总距离。第2步，从已标号节点（已解节点）出发，找出与已标号节点紧邻的所有未解节点，若，则将标号，成为已解节点。第3步，重复第2步，直到成为已解节点。在实际的标号过程中，可以对每个新的已解节点，将所有与其相邻的未解节点，在图上标号，再在所有未标定的标号中路径最短的标号标定，即成为这样一个过程：第1步，对每个与直接相连的节点，标号，表示从已解节点到
3、的路径距离为。将其中路径距离最小的，标定为。第2步，如果是已解节点，则结束；否则，所有与已解节点直接相连的未解节点都是候选点，对每个这样的点，得到所有新的标号，其中是新的已解节点。计算所有未解节点中具有最小的节点，假设相应的标号为，则将其标定为，即成为新的已解节点，其最短路径的前一节点是。第3步，重复第2步。标定后，可以从开始，循着有*的标记的节点就可以得到到的最短路。资料6.11求下图中到的最短路径58v2v4v0v5311696710v1v3图6-3点与点之间的连接路径第1步，已解节点为，与相连的是，得到它们的标号，并将标定；v2v4v0v5311696
4、710v1v3（v0,3）*（v0,5）58图6-4成为已解节点第2步，对新的已解节点，与它相连的未解节点是，得到它们的标号（注意有新的标号），{4,5,13,19}中4最小，所以得到标定；v2v4v0v5311696710v1v3（v0,3）*（v0,5）（v1,4）*5（v1,13）8（v1,19）图6-5成为已解节点第3步，对新的已解节点，与它相连的未解节点是，同样可以得到它们新的标号，得到标定；v2v4v0v5311696710v1v3（v0,3）*（v0,5）（v1,4）*5（v1,13）（v2,11）*（v1,19）（v2,12）8图6-6成为已
5、解节点v2v4v0v5311696710v1v3（v0,3）*5（v1,13）（v2,11）*（v1,19）（v3,20）（v2,12）*8第4步，对新的已解节点，与它相连的未解节点是，得到新的标号，得到标定；（v0,5）（v1,4）*图6-7成为已解节点第5步，对新的已解节点，与它相连的未解节点唯有，给添加新的标号后，得到它的标定为。v0（v0,5）（v1,4）*v2v4v5311696710v1v3（v0,3）*5（v1,13）（v2,11）*（v1,19）（v3,20）（v4,18）*（v2,12）*8图6-8成为已解节点从标定中知道的前一节点为，的前
6、一节点为，的前一节点为，的前一节点为，这样就得到了从到的最短路径为，总长度为18。
