对有向赋权图G,其邻接矩阵A=(an),其中: 若(v,v,)∈E,且n为其权 0 若i= 石(v,V1)gE 无向赋权图的邻接矩阵可类似定义 2 0 2∞ A=208 o805v 5 7350 返回
对有向赋权图Ｇ，其邻接矩阵 = ( ) A ai j ，其中： = = v v E i j w v v E w a i j i j i j i j i j ( , ) 0 ( , ) , 若 若 若 且 为其权 无向赋权图的邻接矩阵可类似定义． A= 4 3 2 1 1 2 3 4 7 3 5 0 8 0 5 2 0 8 3 0 2 7 v v v v v v v v 返回
最短路问题及其算法 一、基本概念 二、固定起点的最短路 三、每对顶点之间的最短路 返回
最 短 路 问 题 及 其 算 法 一、 基 本 概 念 二、固 定 起 点 的 最 短 路 三、每 对 顶 点 之 间 的 最 短 路 返回
基本概念 定义1在无向图G(VE)中: (1)顶点与边相互交错且H(e1)=v21v1(i=1,2,…k)的有限非空序列 =(voe1ve2… Vk-lekvk)称为一条从到k的通路,记n (2)边不重复但顶点可重复的通路称为道路,记为 (3)边与顶点均不重复的通路称为路径,记为 通路Wnm=vge44e2e1ve4v4 道路T, e,veve veve 5 路径P,=V1e1v2e5V4
基 本 概 念 通路 1 4 1 4 4 5 2 1 1 4 4 W v e v e v e v e v v v = 道路 1 4 1 1 2 5 4 6 2 2 3 3 4 T v e v e v e v e v e v v v = 路径 1 4 1 1 2 5 4 P v e v e v v v = 定义１ 在无向图 G=(V,E, )中： （１）顶点与边相互交错且 i i i e v v1 ( ) = − (i=1,2,…k)的有限非空序列 ( ) 0 1 1 2 k 1 k k w v e v e v e v = − 称为一条从0 v 到k v 的通路，记为 k Wv v0 （２）边不重复但顶点可重复的通路称为道路，记为 k Tv v0 （３）边与顶点均不重复的通路称为路 径，记为 k Pv v0
定义2(1)任意两点均有路径的图称为连通图 (2)起点与终点重合的路径称为圈 (3)连通而无圈的图称为树 定义3(1)设P(u)是赋权图G中从u到v的路径, 则称1(P)=∑m(e)为路径P的权 e∈E(P) (2)在赋权图G中,从顶点u到顶点ⅴ的具有最小权的路 P(,v),称为u到v的最短路 返回
定义２ （１）任意两点均有路径的图称为连通图． （２）起点与终点重合的路径称为圈． （３）连通而无圈的图称为树． 定义３ （１）设 P (u,v)是赋权图 G 中从 u 到 v 的路径， 则称 = ( ) ( ) ( ) e E P w P w e 为路径 P 的权． (2) 在赋权图 G 中，从顶点 u 到顶点 v 的具有最小权的路 ( , ) * P u v ，称为 u 到 v 的最短路． 返回
固定起点的最短路 最短路是一条路径,且最短路的仼一段也是最短路. 假设在u0-v0的最短路中只取一条,则从0到其 余顶点的最短路将构成一棵以u为根的树 因此,可采用树生长的过程来求指定顶点到其余顶点 的最短路
固 定 起 点 的 最 短 路 最短路是一条路径，且最短路的任一段也是最短路． 假设在u0-v0的最短路中只取一条，则从u0到其 余顶点的最短路将构成一棵以u0为根的树． 因此, 可采用树生长的过程来求指定顶点到其余顶点 的最短路．