ypedef struct i vexnode typedef vexnode Graph(n]; /foyd算法,求最短路径 void floyd( Graph G, float A[nJ[n], int p[[)) int l j, k; for(l=0,1<n++) for(j=0; j<n: j++) A[0=G[0; PIlDF-1; for(k=0; k<n; k++) for(I=0; I<n; 1++) if(AD(k+A(kIlD pIG=A[k]+A(kJ0 假设以一个带权有向图表示某一区域的公交线路网,途中顶点表示一些区域中 的重要场所,弧代表以有的公交线路,弧上的权代表该线路上的票价(或搭乘所要 的时间)。试设计一个交通指南系统,直到来咨询者以最低的票价活最少的时间从 区域中的某一场所到达另一场所。 实现提示 该问题可以归结为一个求带权有向图中顶点间最短路径的问题。 分别建立以票价后搭乘时间为权的邻结矩阵,以 FLOYD算法来求最短路经济起路 径长度。 设图G=(VE)的顶点集合V=(0,1,,n-1},图用邻接矩阵表示。一开始, 若弧(I,矩阵A进行n次迭代来计算每队顶点间的最短路径,迭代过程中得到的 个矩阵序列AO,A1,…An矩阵元素Anj的值即为从顶点I到顶点j的最短路径长 度。首先在路径(Ij)中插入顶点0,考虑路径(,0j),若该路径存在,即图中有 弧<I,0>和<0j>,比较路径(Lj)和路径(L,0j)的长度,取长度最短者为当前求得的 从顶点I到顶点j且中间顶点编号不大于0的最短路径,、记为(I,……j),其长度存 于A1[I中,然后再考虑路径(L,…,1,…j),由于(1,…j)和(L-…,1,…j)是从顶 点I到顶点1即从顶点1到顶点j中间顶点编号不大于1的最短路径,比较路径(,…,1) 和路径(L-…,1,…j)的长度,若后者较短,则路径(1,,1,j)即为当前求得的从 顶点I到顶点j中间顶点编号不大于1的最短路径,其长度存于A2中,…… 以此类推,逐个插入图的每个顶点,最后必将求得顶点I到顶点j且中间顶点编号 不大于n-1的最短路径。在k+1次迭代时,矩阵Ak+1[lj的值为:typedef struct { char vtx; edgenode*link; }vexnode; typedef vexnode Graph[n]; /floyd 算法，求最短路径 void floyd(Graph G, float A[n][n],int p[n][n]) { int I,j,k; for(I=0;I<n;I++) for(j=0;j<n;j++) { A[I][j]=G[I][j]; P[I][j]=-1; } for(k=0;k<n;k++) for(I=0;I<n;I++) for(j=0;j<n;j++) if(A[I][k]+A[k][j]) { p[I][j]=A[I][k]+A[k][j]; } } 3． 假设以一个带权有向图表示某一区域的公交线路网，途中顶点表示一些区域中 的重要场所，弧代表以有的公交线路，弧上的权代表该线路上的票价（或搭乘所要 的时间）。试设计一个交通指南系统，直到来咨询者以最低的票价活最少的时间从 区域中的某一场所到达另一场所。 [实现提示] 该问题可以归结为一个求带权有向图中顶点间最短路径的问题。 分别建立以票价后搭乘时间为权的邻结矩阵，以 FLOYD 算法来求最短路经济起路 径长度。 设图 G=(V,E)的顶点集合 V={0,1,…., n-1},图用邻接矩阵表示。一开始， 若弧〈I,矩阵 A 进行 n 次迭代来计算每队顶点间的最短路径，迭代过程中得到的一 个矩阵序列 A0,A1,…..,An,矩阵元素 An[i,j]的值即为从顶点 I 到顶点 j 的最短路径长 度。首先在路径（I ,j）中插入顶点 0，考虑路径（I,0,j），若该路径存在，即图中有 弧<I,0>和<0,j>,比较路径（I,j）和路径（I,0,j）的长度，取长度最短者为当前求得的 从顶点 I 到顶点 j 且中间顶点编号不大于 0 的最短路径，、记为（I,…..j）,其长度存 于 A1[I,j]中，然后再考虑路径（I,…,1,…j）,由于 （I,…..j）和（I,…,1,…j）是从顶 点I 到顶点1即从顶点1到顶点j中间顶点编号不大于 1的最短路径，比较路径(I,…,1) 和路径 （I,…,1,…j）的长度，若后者较短，则路径（I,…,1,…j）即为当前求得的从 顶点 I 到顶点 j 中间顶点编号不大于 1 的最短路径 ，其长度存于 A2[I,j]中，………， 以此类推，逐个插入图的每个顶点，最后必将求得顶点 I 到顶点 j 且中间顶点编号 不大于 n-1 的最短路径。在 k+1 次迭代时，矩阵 Ak+1[I,j]的值为：