OPSF之迪杰斯特拉算法ppt课件.ppt

《OPSF之迪杰斯特拉算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、——Dijkstra算法OSPF之最短路径算法一、应用背景（1）应用背景——管道铺设、线路安排、厂区布局、设备更新、网络拓扑等。（2）现实生活中的网络拓扑，可以抽象成由节点（路由器）和边（路由器之间的链路）构成的有向连通图，链路的代价可以抽象成边的权函数。之所以称图为有向图，是因为同一条链路（边）不同方向的权值可能不一样。“单源最短路径”问题：已知一个有n个节点(V0..n)构成的有向连通图G＝（V，E），以及图中边的权函数C(E)，其中V代表节点集合，E表示所有边的集合，并假设所有权非负，求由G中指定节点V0到其他各个节点的最短路径。Dijkstra算法

2、是很经典的求解上述问题的算法，其基本想法是设计一种最短路径树的构造方法，按非降次序逐条构造从V0到各个节点的最短路径.二、最短路算法1．D氏标号法（Dijkstra）；边权非负2.列表法（福德法）；有负权，无负回路4v1v2v3v4v6v5v7225614134121．D氏标号法（Dijkstra）（1）求解思路——从始点出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的。（2）使用条件——网络中所有的弧权均非负，即。（3）选用符号的意义：①P标号（Permanent固定/永久性标号）——从始点到该标号点的最短路权②T标号（Temporary临时性标号

3、）——从始点到该标号点的最短路权上界（4） 计算步骤及例子：第一步：给起始点v1标上固定标号,其余各点标临时性标号T(vj)=,j1;=l1j第二步：考虑满足如下条件的所有点①与v1相邻的点，即;②具有T标号，即，为T标号点集.修改的T标号为，并将结果仍记为T(vj)。svjÎ若网络图中已无满足此条件的T标号点，停止计算。第三步：令,然后将的T标号改成P标号，转入第二步。此时，要注意将第二步中的改为。通俗易懂的步骤：(1)初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为"起点s到该顶点的距离"[例如，U中顶点v的距离为(s,v)的长度

4、，然后s和v不相邻，则v的距离为∞。(2)从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。(3)更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。(4)重复步骤(2)和(3)，直到遍历完所有顶点。237184566134105275934682求从1到8的最短路径237184566134105275934682X={1}min{d12,d14,d16}=min{0+2,0+1,0+

5、3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0237184566134105275934682X={1,4}min{d12,d16,d42,d47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},p2=2p1=0p4=1p2=2237184566134105275934682X={1,2,4}min{d16,d23,d25,d47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},p6=3p2=2p4=1p1=0p6=32371845661

6、34105275934682X={1,2,4,6}min{d23,d25,c47,d67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},p7=3p2=2p4=1p1=0p6=3p7=3237184566134105275934682X={1,2,4,6,7}min{d23,d25,d75,d78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6237184566134105275934682

7、X={1,2,4,6,7}min{d23,d53,d58,d78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8X={1,2,3,4,5,6,7},p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8237184566134105275934682X={1,2,3,4,6,7}min{d38,d58,d78}=min{8+6,6+4,3+7}=min{14,10,11}=10X={1,2,3,4,5,6,7,8},p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134

8、105275934682X={1,2,3,4,6,7,8}1到8的