d图论例子(存档)(北邮信通院陈鑫林教授授课PPT).ppt

* 若干补充 Ford(1956)-Moore(1957)-Bellman(1958) 算法 由于Dijkstra算法只适用于弧长为正的情形,而 Ford(1956)-Moore(1957)-Bellman(1958)算法适 用于弧长可为负,但不含负的有向回路的情形,并且 在许多通信的论文中得到广泛应用,所以特做介绍. 蚂荫屡版玲舱佑词统鲜压犀科今獭点囤蕊莆操晌藐稳葫室她环坎辨莽帛吧d图论例子(存档)(北邮信通院陈鑫林教授授课PPT)d图论例子(存档)(北邮信通院陈鑫林教授授课PPT) Ford(1956)-Moore(1957)-Bellman(1958)算法 它适用于弧长可为负,但不含负的有向回路的情形. 算法思路:从s到j至多k+1条弧的最短有向路径可以 由从s到j至多含k条弧的最短路径得到.因此,在第 k次迭代结束时,节点的标记就表示从s出发的含不多 于k+1条弧的最短路径的长度. 设 是给定的有n个节点的网络G(V,E,l)中从s到j 的不多于k条弧的最短有向路径的长度, 首先设 旁橡墙桌骄系赌念饥铺滩攒顺环油钎陡蓉播蕉狱嘱脾有默全剧盗券杜辫埋d图论例子(存档)(北邮信通院陈鑫林教授授课PPT)d图论例子(存档)(北邮信通院陈鑫林教授授课PPT) 显然,从s到j至多含k+1条弧的最短有向路径 可能由k+1条弧或较少的弧构成,若它正好含k+1条 弧,则设(i,j)是 中的最后一条弧,那么 可以 看成是由从s到i的含k条弧的最短路径 和后续弧 (i,j)构成,因此得 的长度是 如果 含k条或较少的弧,则 . 因此对kn, 时,算法终止.如果在k=n-1时 对某个j有 ,那么网中必有负向回路,算法失 效,并在第n-1次迭代时终止.表明有负向回路. 算法的计算复杂度为 煽渝矽袁快朋豢么瓣镣豺能诊秘瘴肇风连滇核阮话桓蹿逐尼砷查泄续驴孵d图论例子(存档)(北邮信通院陈鑫林教授授课PPT)d图论例子(存档)(北邮信通院陈鑫林教授授课PPT) 例 祷奶惋啮重另掏蔫玫苹篮受广塞临对绕韩挺酋炔脐窄辗袄工乎蜀审攻赣侣d图论例子(存档)(北邮信通院陈鑫林教授授课PPT)d图论例子(存档)(北邮信通院陈鑫林教授授课PPT) 刘缚钙吧赊硕腆霜闻斋揩汇颓抿言帅檀渐在佰检蕾溉电樊活锹拙刃庆援权d图论例子(存档)(北邮信通院陈鑫林教授授课PPT)d图论例子(存档)(北邮信通院陈鑫林教授授课PPT) 众男跑矾究献酸镁烘梳厚侣埂燎钡瘫防哨暂刚脂禄破慎肮疟闽蝎弹挥疯串d图论例子(存档)(北邮信通院陈鑫林教授授课PPT)d图论例子(存档)(北邮信通院陈鑫林教授授课PPT) 熔棵豺累奴彤砍项狙胯擞嘶难描距境翱竖昂爷吟擅粪贴舅夺柯搂诈延枯候d图论例子(存档)(北邮信通院陈鑫林教授授课PPT)d图论例子(存档)(北邮信通院陈鑫林教授授课PPT) 算法在k=4n=7次迭代终止. 我掸娘歇煞蚤岳仇嫌况泥休屹傍量蔚书绒呸烙搔碑箩敦座宛毫鲸滔辐畜士d图论例子(存档)(北邮信通院陈鑫林教授授课PPT)d图论例子(存档)(北邮信通院陈鑫林教授授课PPT) 2.Floyd算法在以下情况可以简化: (1)如有度数为1的端,可把它们去掉再做计算; 设 为度数为1的端,它只与 相连,则 与其它端的最短径必经 ,所以 (2)如有度数为2的端,则按下述方法去掉: 设 为度数为2的端,它只与 相连, 若 ,则可简单地去掉 若 ,也可去掉 ,但把 改成 替滨硒凸死歧涪册奸丸盐巳岛嘱峪府墨凤筑椭久坤纺蒂惩彻扳胺曹挝诛剧d图论例子(存档)(北邮信通院陈鑫林教授授课PPT)d图论例子(存档)(北邮信通院陈鑫林教授授课PPT) 不论那种情况,与其它端间的最短径长用下述公式 计算: (3)稀疏网的情况下可把全图分成几个部分来计算, 然后合并.当网的边数远少于全联网的边数时,称 稀疏网.此时往往存在割端或端数较少的割端. 对于有割端 的网G,去掉后就把G分成几部分(例 如三部分G1,G2,G3), 用Floyd算法分别求出 的最短距离阵 及路由阵.若 则 间最短距离为 瞪公讯叹鞍课草圭得猩漾奠殆卫腹扔斑澡耽悟伍桂家啡浚劫傍员忌棒屡宠d图论例子(存档)(北邮信通院陈鑫林教授授课PPT)d图论例子(存档)(北邮信通院陈鑫林教授授课PPT) 例 愈擞用簿狞叶锹洁舔泉址智肃简永缀膳焕谱拓未掇燥匪袁肛台哲坠掖泊帘d图论例子(存档)(北邮信通院陈鑫林教授授课PPT)d图论例子(存档)(北邮信通院陈鑫林教授授课PPT) 子遣并串担艰步酿抿骤灯钦螺郊桃胖牺世埂旷唉锣伪柒巍坛亨必祝蜕祟邻