通信网基础 第6章 路径选择算法.pdf

文档介绍：: .
vj划归到Gp j j i ij
vjp& G-G
vGip&
以新G 中的节点作为转接点，计算并修改（G-G ）中的w *
p p j 选定所有w j的最小值，并将其划归到Gp中：
w=min w* 得到新的
i j ， Gp
vjp& G-G
vj与vs直连且 d=si min dsj
vjP& G-G
N
Gp =n
将 划归到 中，即新的
vi Gp G p = {vs ,vi} ，wi = dsi Y
所有节点被置定，算法终止路径选择算法
F算法
F算法背景知识
F算法使用距离矩阵和路由矩阵。
距离矩阵是一个n╳n矩阵，以图G的n个节点为行和
列。记为W=[wij ] n ╳ n， wij表示图G中vi和vj两点之间
的路径长度。
路由矩阵是一个n╳n矩阵，以图G的n个节点为行和
列。记为R =[rij ] n ╳ n ，其中rij表示vi至vj经过的转接
点（中间节点）。路径选择算法
F算法范例
v3

v2
v7 v6

v4


v1 v5路径选择算法
F算法范例
& 0 ' ' ' # &0 0 0 4 5 0 7#
$ ! $0 0 0 4 0 6 7!
$ ' 0 ' 5 ' 2 ! $ !
$ ' ' 0 ' ' 4 ! $0 0 0 0 0 6 7!
1 $ ! $ !
W