Dijkstra最短路径算法

1、Dijkstra最短路径算法最短路径算法在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：（）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。（）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。（）确定起点终点的最短路径问题：即已知起点和终点，求两结点

2、之间的最短路径。（）全局最短路径问题：求图中所有的最短路径。用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnso下面我们主要研究Dijkstra算法 Dijkstra算法：也称为最短路径算法（ShortestPathAlgorithm）、正向搜索算法（ForwardSearchAlgorithm），是一种集中式的静态算法。 Dijkstra算法的正式定义： 设：N=网络中所有节点的集合S=源节点M=已有算法归并的节点的集合L(i,j)=节点i与

3、j之间链路权值；若两个节点间没有直接连接则为C(n)=算法求得的当前从S到n的最少花费路由的花费 算法步骤：1. 初始化M=SC(n)=L(S,n)fornS2. 从不再M中的相邻节点中找到出一个具有和节点S的最少花费路由的节点，并且把节点规约进M中。3. 更新最少的花费路径4. 重复步骤2和3，知道M=N.Dijkstra算法实现1.每个结点用从源结点沿已知最佳路径到本结点的距离来标注，标注分为临时性标注和永久性标注；2.初始时，所有结点都为临时性标注，标注为无穷大；3.将源结点标注为0，且为永久性标注，并令其为工作结点；4.检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点

4、的标注之和小于该结点的标注，则用新计算得到的和重新标注该结点；5.在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点，并成为下一轮检查的工作结点；6.重复第四、五步，直到目的结点成为工作结点；57.2.2最佳路由算法 Dijkstra算法例H(,-)D(,-)D(,-)B(2,A)ABCDEFGHAB(2,A)C(,-)D(,-)E(,-)F(,-)G(6,A)H(,-)2732232246AB(2,A)C(9,B)E(4,B)F(6,E)G(5,E)AB(2,A)C(9,B)G(5,E)H(8,F)AB(2,A)C(9,B)D(,-)E(4,B)F(6,E)G(5,E)H(9,G)AC(9,B)D(,-)E(4,B)F(,-)G(6,A)H(,-)E(4,B)F(6,E)(a)(b)(c)(d)(e)(f)6从A出发到D的最短路径 sRBDBRCDCRDDDREDERFDFRGDGRHDHUB,C,D,E,F,G,HA20000A60BC,D,E,F,G,HA2B90B40A60ED,F,G,HA2B90B4E6E