赋权图和距离 ■赋权图：G=<V,E,w> 3 ●V:顶点的有限集合 VS ●E:边的有限集合 ●w:赋权函数，E→ -w(e):边e的权 2023/4/10
n 赋权图：G = <V, E, w> l V：顶点的有限集合 l E：边的有限集合 l w：赋权函数， E à R – w(e)：边e的权 2023/4/10 6 赋权图和距离
赋权图和距离 ■邻接矩阵 ·引入特殊数值（∞）表示不相邻 3 2 9 V6 013004 0000 1 00 2 0 3 2 2 6 00 1 40∞ 2 00 0 00 0 33 P 1 6 2 3 202 00000 200200 2023/4/10
n 邻接矩阵 l 引入特殊数值（∞）表示不相邻 2023/4/10 7 赋权图和距离
赋权图和距离 ■邻接矩阵 ·引入特殊数值（∞）表示不相邻 ■关联矩阵 13004 0∞ 1 6 200 3 00 2 00 2 00 4 1 4 00 2 P % 0 88 6 6 22 3 1 88 88 8 P 4 1 00 2 00 2023/4/10
n 邻接矩阵 l 引入特殊数值（∞）表示不相邻 n 关联矩阵 2023/4/10 8 赋权图和距离
赋权图和距离 ■邻接矩阵 ·引入特殊数值（∞）表示不相邻 ■关联矩阵 ■邻接表 13 004 0000 顶点（邻点，边权）列表 1 2 0 6 00 U (2,1,(g,3),(5,4) 3 的 (1,1,(e4,2) 2 1 88 内 (,3,(6,2) 00 3 (2,2),(5,5),(6,1),(v8,4 00 2 (1,4,(,2),(4,5),(,2,(g,2) b 3 2 (4,1),(g,3),(g,2) 88 6 9 (,2,(8,1) 6 2 3 P 2 g (U4,4,(,2),(6,3),(7,1),(g,2 00 00 2 2 g (6,2,(g,2) 2023/4/10
n 邻接矩阵 l 引入特殊数值（∞）表示不相邻 n 关联矩阵 n 邻接表 2023/4/10 9 赋权图和距离
赋权图和距离 ■（赋权）长度 ● 经过的边的权和 2023/4/10 10
n （赋权）长度 l 经过的边的权和 2023/4/10 10 赋权图和距离