文档介绍：Dijkstra最短路径算法
最短路径算法
在日常生活中,我们如果需要常常往返A地区和B地区之间,我们最希望知道的可能是从A地区到B地区间的众多路径中,那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。算法具体的形式包括:
(1)确定起点的最短路径问题:即已知起始结点,求最短路径的问题。
(2)确定终点的最短路径问题:与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题
完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
(3)确定起点终点的最短路径问题:即已知起点和终点,求两结点之间的最短路径。
(4)全局最短路径问题:求图中所有的最短路径。
用于解决最短路径问题的算法被称做“最短路径算法”, 有时被简称作“路径算法”。最常用的路径算法有:Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnso
下面我们主要研究Dijkstra算法
Dijkstra算法:也称为最短路径算法(Shortest Path Algorithm )、正向搜索算法(Forward Search Algorithm),是一种集中式的静态算法。
Dijkstra算法的正式定义:
设:N = 网络中所有节点的集合
S = 源节点
M = 已有算法归并的节点的集合
L(i,j) = 节点i与j之间链路权值;若两个节点间没有直接连接则为∞
C(n) = 算法求得的当前从S到n的最少花费路由的花费
算法步骤:
初始化
M={S}
C(n)=L(S,n) for n≠ S
从不再M中的相邻节点中找到出一个具有和节点S的最少花费路由的节点,并且把节点规约进M中。
更新最少的花费路径
重复步骤 2 和 3 ,知道M=N.
Dijkstra算法实现
每个结点用从源结点沿已知最佳路径到本结点的距离来标注,标注分为临时性标注和永久性标注;
初始时,所有结点都为临时性标注,标注为无穷大;
将源结点标注为0,且为永久性标注,并令其为工作结点;
检查与工作结点相邻的临时性结点,若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注,则用新计算得到的和重新标注该结点;
在整个图中查找具有最小值的临时性标注结点,将其变为永久性结点,并成为下一轮检查的工作结点;
重复第四、五步,直到目的结点成为工作结点;
5
最佳路由算法
Dijkstra算法例
H(,-)
D(,-)
D(,-)
B(2,A)
A
B
C
D
E
F
G
H
A
B(2,A)
C(,-)
D(,-)
E(,-)
F(,-)
G(6,A)
H(,-)
2
7
3
2
2
3
2
2
4
6
A
B(2,A)
C(9,B)
E(4,B)
F(6,E)
G(5,E)
A
B(2,A)
C(9,B)
G(5,E)
H(8,F)
A
B(2,A)
C(9,B)
D(,-)
E(4,B)
F(6,E)
G(5,E)
H(9,G)
A
C(9,B)
D(,-)
E(4,B)
F(,-)
G(6,A)
H(,-)
E(4,B)
F(6,E)
(a)
(b)
(c)
(d)
(e)
(f)