具有负权的最短路问题求解过程.doc

《具有负权的最短路问题求解过程.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、具有负权的最短路算法给每一个点一个标号，标号由两部分组成。后一部分表示从起点到该点的临时最短距离；前一部分表示从起点到该点的临时最短路线上的前一点。我们每进行一轮，都去修改标号中的值，直到进行到某一轮，所有标号中的值都不发生变化了，就得到了起点到各个点的最短距离和最短路线。在这里，设d(t)(vs,vj)为第t轮由起点vs到点vj的临时最短距离。（t可以理解为第t轮，也可以理解为temporary的第一个字母t，表示临时的意思）（1）令第1轮的临时最短距离为：d(1)(vs,vj)=ωsj；（2）求解第2轮中从起点vs

2、到点vj的临时最短距离d(2)(vs,vj)。对于点vj，计算d(2)(vs,vj)=mini{d(1)(vs,vi)+ωij}也就是说从vs到vj可以分2步走，第一步，先从vs到vi，第二步，从vi到vj。因此，假如一个图有n个点，对每一个点就有n种路线可选择，我们在这n种路线中找出距离最短的作为该点的临时最短距离。在每一轮中，我们都需要计算(n-1)n次才能够找到从起点到每一个点的最短距离（起点不需要计算），假如一个有向图包含的点很多时，计算量将很大。由于当vi和vj之间不存在弧时，ωij=∞，因此我们只需找出终点

3、在该点的所有弧，用所有弧的弧长加上这些弧的起点的临时最短距离，其中的最小者如果比该点的标号值小，就设为该点新的临时最短距离；对于第t轮中从起点vs到点vj的临时最短距离为d(t)(vs,vj)，则对于点vj，有d(t)(vs,vj)=mini{d(t-1)(vs,vi)+ωij}当进行到第k轮时，所有点的标号经过计算都不再发生变化时，即d(k)(vs,vj)=d(k-1)(vs,vj)就得到了起点vs到各点的最短路距离。