第8章图 p=iq= disJoint[p];max=- MaxNum;m从j到k找权值最大的边t,t) while(q<=k)i if( Edge[q][p]> max)( max= Edgeqllpl: tl =p; t2=q: j if max Edge[sll[s2))( max= Edge[s1[s2]: kl=sI: k2=$2: if max Edgetl[e2))( max=Edge[tl[t2]: kl=tl; k2=22;1 if max I= Edge) ∥当Edge]=max时边不改 if( disJoint( k1]=k2 )disJoint(1]=-1: else disJoint[ k2=-1; ∥删除权值最大的边 ∥加入新的边 Edge[l0=-Edgeblo: 8-15以右图为例,按 Dijkstra算法计算得到的从顶点α(A)到其它各个顶点的最短路径和最短路径长度 【解答】 源点终点 最短路径 AB(AB(AB)(AB)AB回Ba5 C_L(AC⊥L(AC) B, D)I(A, B, D (A, B, D, E)(A, B, D 8-16在以下假设下,重写 Dijkstra算法: (1)用邻接表表示带权有向图G,其中每个边结点有3个域:邻接顶点 vertex,边上的权值 length 和边链表的链接指针link (2)用集合T=V(G)-S代替S(已找到最短路径的顶点集合),利用链表来表示集合T。 试比较新算法与原来的算法,计算时间是快了还是慢了,给出定量的比较 【解答】 (1)用邻接表表示的带权有向图的类定义 const int DefaultS ize= 10: ∥缺省顶点个数 ∥图的前视类定义 struct Edge i 的定义 friend class Graph ∥边的另一顶点位置 ∥边上的权值 下一条边链指针 Edge (0 ∥构造函数 Edge( int num, float wh ) vertex(num), length(wh), link(NULL) ∥构造函数第 8 章 图 107 } p = j; q = disJoint[p]; max = -MaxNum; //从 j 到 k 找权值最大的边(t1, t2) while ( q <= k ) { if ( Edge[q][p] > max ) { max = Edge[q][p]; t1 = p; t2 = q; } p =q; q = disJoint[p]; } max = Edge[i][j]; k1 = i; k2 = j; if ( max < Edge[s1][s2] ) { max = Edge[s1][s2]; k1 = s1; k2 = s2; } if ( max < Edge[t1][t2] ) { max = Edge[t1][t2]; k1 = t1; k2 = t2; } if ( max != Edge[i][j] ) { //当 Edge[i][j] == max 时边不改 if ( disJoint[k1] == k2 ) disJoint[k1] = -1; else disJoint[k2] = -1; //删除权值最大的边 disJoint[j] = i; //加入新的边 Edge[j][i] = - Edge[j][i]; } } } 8-15 以右图为例，按 Dijkstra 算法计算得到的从顶点①(A)到其它各个顶点的最短路径和最短路径长度。 【解答】 源点 终点 最短路径 最短路径长度 A B (A,B) (A,B) (A,B) (A,B) 10 10 10 10 C (A,C) (A,C) (A,C) (A,C) 18 18 18 18 D ⎯ (A,B,D) (A,B,D) (A,B,D)  15 15 15 E ⎯ ⎯ (A,B,D,E) (A,B,D,E)   17 17 8-16 在以下假设下，重写 Dijkstra 算法： (1) 用邻接表表示带权有向图 G，其中每个边结点有 3 个域：邻接顶点 vertex，边上的权值 length 和边链表的链接指针 link。 (2) 用集合 T = V(G) - S 代替 S (已找到最短路径的顶点集合)，利用链表来表示集合 T。 试比较新算法与原来的算法，计算时间是快了还是慢了，给出定量的比较。 【解答】 (1) 用邻接表表示的带权有向图的类定义： const int DefaultSize = 10; //缺省顶点个数 class Graph; //图的前视类定义 struct Edge { //边的定义 friend class Graph; int vertex; //边的另一顶点位置 float length; //边上的权值 Edge *link; //下一条边链指针 Edge ( ) { } //构造函数 Edge ( int num, float wh ) : vertex (num), length (wh), link (NULL) { } //构造函数 10 18 5 5 2 2 2 A B C D E