最短路问题__迪杰斯特拉算法.ppt
《最短路问题__迪杰斯特拉算法.ppt》由会员分享,可在线阅读,更多相关《最短路问题__迪杰斯特拉算法.ppt(19页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、最最短短路路问问题题一、问题的提法及应用背景一、问题的提法及应用背景(1)问问题题的的提提法法寻寻求求网网络络中中两两点点间间的的最最短短路路就就是是寻寻求求连连接接这这两两个个点点的的边边的的总总权权数数最最小小的的通通路路。(注注意意:在在有有向向图图中中,通通路路开开的的初初等等链链中中所所有有的的弧弧应应是是首尾相连首尾相连的。)的。)(2)应应用用背背景景管管道道铺铺设设、线线路路安安排排、厂区布局、设备更新等。厂区布局、设备更新等。二、最短路算法二、最短路算法1 D氏标号法(氏标号法(Dijkstra);边权非负);边权非负2.2.列表法(福德法);有负权,无负回路列表法(福德法)
2、;有负权,无负回路4v1v2v3v4v6v5v7225614134121D氏标号法(氏标号法(Dijkstra)(1 1)求解思路)求解思路从始点出发,逐步从始点出发,逐步顺序顺序地向外探寻地向外探寻,每向外延伸一步都要求是每向外延伸一步都要求是最最短的。短的。(2 2)使用条件)使用条件网络中网络中所有的弧权所有的弧权均均 非负非负,即,即 。(3 3)选用符号的意义)选用符号的意义:P P 标号标号(Permanent固定固定/永久性标号)永久性标号)从始点到该标号点的最短路权从始点到该标号点的最短路权 T T 标号标号(Temporary临时性标号)临时性标号)从始点到该标号点的最短路权
3、从始点到该标号点的最短路权上界上界(4 4)计算步骤及例子:计算步骤及例子:第第一一步步:给给起起始始点点v1标标上上固固定定标标号号,其其余各点标临时性标号余各点标临时性标号T(vj)=,j 1;=l1j第二步第二步:考虑满足如下条件的所有点:考虑满足如下条件的所有点与与v1相邻的点,即相邻的点,即;具有具有T 标号,即标号,即,为为T 标号点集标号点集.修修改改的的T标标号号为为,并并将将结结果仍记为果仍记为T(vj)。svjv若网络图中已无满足此条件的若网络图中已无满足此条件的T标号点,停止计算。标号点,停止计算。第第三三步步:令令,然然后后将将的的T 标标号号改改成成P 标标号号,转转
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 短路 问题 _ 迪杰斯特拉 算法
限制150内