OPSF之迪杰斯特拉算法

——Dijkstra算法一、应用背景（1）应用背景——管道铺设、线路安排、厂区布局、设备更新、网络拓扑等。（2）现实生活中的网络拓扑，可以抽象成由节点（路由器）和边（路由器之间的链路）构成的有向连通图，链路的代价可以抽象成边的权函数。之所以称图为有向图，是因为同一条链路（边）不同方向的权值可能不一样。“单源最短路径”问题：已知一个有n个节点(V0..n)构成的有向连通图G＝（V，E），以及图中边的权函数C(E)，其中V代表节点集合，E表示所有边的集合，并假设所有权非负，求由G中指定节点V0到其他各个节点的最短路径。Dijkstra算法是很经典的求解上述问题的算法，其基本想法是设计一种最短路径树的构造方法，按非降次序逐条构造从V0到各个节点的最短路径.二、最短路算法1．D氏标号法（Dijkstra）；边权非负2.列表法（福德法）；有负权，无负回路4v1v2v3v4v6v5v7225614134121．D氏标号法（Dijkstra）（1）求解思路——从始点出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的。（2）使用条件——网络中所有的弧权均非负，即。0ijl（3）选用符号的意义：①P标号（Permanent固定/永久性标号）——从始点到该标号点的最短路权②T标号（Temporary临时性标号）——从始点到该标号点的最短路权上界（4）计算步骤及例子：0)(1vp第一步：给起始点v1标上固定标号,其余各点标临时性标号T(vj)=,j1;=l1jjvsjvAvvj),(1第二步：考虑满足如下条件的所有点①与v1相邻的点，即;②具有T标号，即，为T标号点集.修改的T标号为，并将结果仍记为T(vj)。svjjv})(),(min{11jjlvpvT若网络图中已无满足此条件的T标号点，停止计算。第三步：令,然后将的T标号改成P标号，转入第二步。此时，要注意将第二步中的改为。1v0jv0jv)}({min)(0jsvjvTvTj通俗易懂的步骤：(1)初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为起点s到该顶点的距离[例如，U中顶点v的距离为(s,v)的长度，然后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+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=3237184566134105275934682X={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=6237184566134105275934682X={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=10237184566134105275934682X={1,2,3,4,6,7,8}1到8的最短路径为{1，4，7，5，8}，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10已完成结点集S,本次最近点ABCDEF1{}DistancePath2DistancePath3DistancePath4DistancePath5(n-1)DistancePathEFDBCA82530181071540181004070158023050BACDEFBACDEF运算过程表邻接矩阵图•数据源——邻接矩阵•已确定结点集S•待选结点集V-S•结点临时最短路径长度——Distance数组•结点临时最短路径——Path数组Dijkstra算法--数据组织已完成结点集，本次最近点ABCDEF1{A,},CDistance0530PathA-1AA-1-12DistancePath3DistancePath4DistancePath5(n-1)DistancePath运算过程表Dijkstra算法—例子EFDBCA82530181071540181004070158023050BACDEFBACDEF邻接矩阵图例：计算从A点出发的单源最短路径已完成结点集，本次最近点ABCDEF1{A,},CDistance0530PathA-1AA-1-12{A,C},FDistance02053012PathACAA-1C3DistancePath4DistancePath5(n-1)DistancePath运算过程表Dijkstra算法—例子EFDBCA82530181071540181004070158023050BACDEFBACDEF邻接矩阵图例：计算从A点出发的单源最短路径已完成结点集，本次最近点ABCDEF1{A,},CDistance0530PathA-1AA-1-12{A,C},FDistance02053012PathACAA-1C3{A,C,F},BDistance0205223012PathACAFFC4DistancePath5(n-1)DistancePath运算过程表Dijkstra算法—例子EFDBCA82530181071540181004070158023050BACDEFBACDEF邻接矩阵图例：计算从A点出发的单源最短路径已完成结点集，本次最近点ABCDEF1{A,},CDistance0530PathA-1AA-1-12{A,C},FDistance02053012PathACAA-1C3{A,C,F},BDistance0205223012PathACAFFC4{A,C,F,B},DDistance0205222812PathACAFBC5(n-1)DistancePath运算过程表Dijkstra算法—例子EFDBCA82530181071540181004070158023050BACDEFBACDEF邻接矩阵图例：计算从A点出发的单源最短路径已完成结点集，本次最近点ABCDEF1{A,},CDistance0530PathA-1AA-1-12{A,C},FDistance02053012PathACAA-1C3{A,C,F},BDistance0205223012PathACAFFC4{A,C,F,B},DDistance0205222812PathACAFBC5(n-1){A,C,F,B,D},EDistance0205222812PathACAFBC运算过程表Dijkstra算法—例子EFDBCA82530181071540181004070158023050BACDEFBACDEF邻接矩阵图例：计算从A点出发的单源最短路径最短路径结点集ABCDEF{A,C,F,B,D,E}Distance0205222812PathACAFBC运算结果Dijkstra算法—例子0181004070158023050BACDEFBACDEF邻接矩阵图EFDBCA8510715•通过Distance数组得到最短路径长度：D:22•通过对Path数组的反向搜索得到最短路径，如D结点相对于源点A的最短路径：DFCA例：计算从A点出发的单源最短路径算法实现：Dijkstra.cppDijkstra算法的主要执行是：◆数组变量的初始化：时间复杂度是O(n)；◆求最短路径的二重循环：时间复杂度是O(n2)；因此，整个算法的时间复杂度是O(n2)。Dijkstra算法—算法分析