原创力文档- 1、本文档共11页，可阅读全部内容。
- 2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
- 5、该文档为VIP文档，如果想要下载，成为VIP会员后，下载免费。
- 6、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
物流信息管理;第五章地理信息系统;最短路径原理与算法;最短路径问题;（一）最短路径的含义
“纯距离”意义上的最短路径
例如，需要运送一批物资从一个城市到另一个城市，选择什么样的运输路线距离最短？“经济距离”意义上的最短路径
例如，某公司在10大港口C1，C2，…，C10设有货栈，从Ci到Cj之间的直接航运价格，是由市场动态决定的。如果两个港口之间无直接通航路线，则通过第三个港口转运。那么，各个港口之间最廉价的货运线路是什么？;“时间”意义上的最短路径
例如，某家经营公司有一批货物急需从一个城市运往另一个城市，那么，在由公路、铁路、河流航运、航空运输等4种运输方式和各个运输线路所构成的交通网络中，究竟选择怎样的运输路线最节省时间？
以上3类问题，都可以抽象为同一类问题，即赋权图上的最短路径问题。
不同意义下的距离都可以被抽象为网络图中边的权值。
权——这种权值既可以代表“纯距离”，又可以代表“经济距离”，也可以代表“时间距离”。;（二）最短路径的算法;标号法的基本思想
设G是一个赋权有向图，即对于图中的每一条边，都赋予了一个权值。在图G中指定两个顶点，确定为起点和终点，不妨设v1为起点，vk为终点。
首先从v1开始，给每一个顶点标一个数，称为标号。这些标号，又进一步区分为T标号和P标号两种类型。其中，每一个顶点的T标号表示从起点v1到该点的最短路径长度的上界，这种标号为临时标号；P标号表示从v1到该点的最短路长度，这种标号为固定标号。
在最短路径计算过程中，对于已经得到P标号的顶
点，不再改变其标号；对于凡是没有标上P标号的顶点，先给它一个T标号；算法的每一步就是把顶点的T标号逐步修改，将其变为P标号。
那么，最多经过k-1步，就可以求得到从起点v1到
每一个顶点的最短路径及其长度。;标号法具体计算步骤
开始，先给v1标上P标号P(v1)＝0，其余各点标上T标号T(vj)＝+∞（j≠1）。
①如果刚刚得到P标号的点是vi，那么，对于所有这样的点
将其T标号修改为：min[T(vj)，P(vi)+wij]。
②若G中没有T标号，则停止。否则，把点的T标号修改为P标号，然后再转???①。
其中， 满足;标号法例子;标号法例子
文档评论（0）