文档介绍：(完整word版)最短路径算法附应用
(完整word版)最短路径算法附应用
(完整word版)最短路径算法附应用
最短路径算法及应用
乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。如果有一张
在下述的Dijstra
方法具体步骤中，用
P，T分别表示某个点的P标号、T标号，si
表
示第i步时，具P标号点的集合。为了在求出从
vs到各点的距离的同时，
也求出从Vs到各
点的最短路，给每个点
v以一个λ值，算法终止时λ(v)=m，表示在Vs到v的最短路上，
v的前一个点是Vm；如果λ(v)=∞，表示图
G中不含从Vs到v的路；λ(Vs)=0。
Dijstra方法的具体步骤：
{初始化}i=0
S0={Vs}，P(Vs)=0λ(Vs)=0
对每一个v<>Vs，令T(v)=+∞，λ(v)=+∞，
k=s
{开始}
①如果Si=V，算法终止，这时，每个v∈Si，d(Vs,v)=P(v)；否则转入②
②考察每个使(Vk,vj)∈E且vjSi的点vj。
如果T(vj)>P(vk)+wkj，则把T(vj)修改为P(vk)+wkj，把λ(vj)修改为k。
③令
如果，则把的标号变为P标号，令
，k=ji，i=i+1，转①，否则终止，这时对每一个v∈Si，d(vs,v)=P(v)，
(完整word版)最短路径算法附应用
(完整word版)最短路径算法附应用
(完整word版)最短路径算法附应用
2/16
(完整word版)最短路径算法附应用
(完整word版)最短路径算法附应用
(完整word版)最短路径算法附应用
而对每一个。
算法实现：
1、数据结构
＊用邻接矩阵表示图G
＊用一维数组D[I]存放从源点到I点的最短路径长度或其上界。（上面算法中的P
标号与T标号实际上存放着源点到某点的最短路径长度或其上界，因此我们可以统一用D
数组来表示）。
＊用一维数组P，其中P[I]记录到I点的最短路径中前一个顶点的序号。
{$R+}
2、源程序
(完整word版)最短路径算法附应用
(完整word版)最短路径算法附应用
(完整word版)最短路径算法附应用
3/16
(完整word版)最短路径算法附应用
(完整word版)最短路径算法附应用
(完整word版)最短路径算法附应用
4/16
(完整word版)最短路径算法附应用
(完整word版)最短路径算法附应用
(完整word版)最短路径算法附应用
（二）Bellman-Ford算法
在单源最短路径问题的某些实例中，可能存在权为负的边。如果图G＝（V，E）不包含
从源s可达的负权回路，则对所有v∈V，最短路径的权定义d(s,v)依然正确，即使它是一
个负值也是如此。但如果存在一从s可达的负回路，最短路径的权的定义就不能成立。S到
该回路上的结点就不存在最短路径。当有向图中出现负权时，则Dijkstra算法失效。当不
存在源s可达的负回路时，我们可用Bellman-Ford算法实现。
下面我们介绍有向图中，存在具有负权的弧时，求最短路的方法