学生作品-带权图的单源最短路径问题说明

1、一、作品要求编写求带权图的单源最短路径程序。二、学生作品分析1、代码分析代码分析如下：public class AdjMatrixGraph extends AbstractGraph类，继承抽象图类/邻接矩阵表示的图protected SeqList vertexlist;/顺序表图的顶点集合protectedprivate final adjmatrix;MAX_WEIGHT =/图的邻接矩阵eger.MAX_VALUE; /最大权值（表示无穷大）/privateedgeCount;/边数?public AdjMatrixGraph(n)/构造方法，n 指定最多顶点数this.vertex

2、list = new SeqList(n);/构造指定容量的空顺序表/构造 n 行 n 列空矩阵/初始化图的邻接矩阵this.adjmatrix = newnn;for (i=0; in; i+)for (j=0; jn; j+)this.adjmatrixij= (i=j) ? 0 : MAX_WEIGHT;/边的权值为 0 或最大权值/this.edgeCount=0;public AdjMatrixGraph(E verti, Edge edges) /以顶点集合和边集合构造一个图this(verti.length);for (i=0; iverti.length; i+)insertV

3、ertex(vertii);/一个顶点for (j=0; jedges.length; j+)insertEdge(edgesj);/一条边public AdjMatrixGraph(SeqList list, Edge edges) /以顶点集合和边集合构造一个图this(list.length();this.vertexlist = list;for (j=0; j=0 & i=0 &jvertexCount() & i!=j &adjmatrixij=MAX_WEIGHT)this.adjmatrixij=weight;/this.edgeCount+;return true;retur

4、n false;publicinsertEdge(Edge edge)/一条边if (edge!=null)return insertEdge(edge.start, edge.dest, edge.weight); return false;public String toString()/获得图的顶点集合和邻接矩阵String str= 顶点集合：+vertexlist.toString()+n;str += 邻接矩阵:n;n = vertexCount();/edgeCount+条边 n;/顶点数for (i=0; in; i+)for(j=0; j=0 & i=0 & j=0 & vn

5、)this.vertexlist.remove(v);/删除顺序表的第 i 个元素，顶点数已减一for (i=v; in-1; i+)for (j=0; jn; j+)this.adjmatrixij = this.adjmatrixi+1j;/元素向前一行移动for (j=v; jn-1; j+)for (i=0; i=0 & v=-1 & wvertexCount() & v!=w)for (j=w+1; j0 & adjmatrixvjMAX_WEIGHT) return j;return -1;public AdjMatrixGraph minSpanTree_prim()姆算法/构造

6、带权图最小生成树的/返回最小生成树相应的图对象Edge mst = new EdgevertexCount()-1;/n 个顶点最小生成树有n-1条边for (i=0; imst.length; i+)发构造最小生成树/初始化 mst 数组，从顶点 v0 出msti = new Edge(0, i+1, adjmatrix0i+1);/保存从顶点 v0 到其他各顶点的边的权System.out.pr(mst 数组初值：); for(j=0; jmst.length; j+)System.out.pr(mstj.toString();/显示 mst 数组的变化过程for (i=0; imst.l

7、ength; i+)/共选出 n-1 条边minweight = MAX_WEIGHT;min = i;/求最小权值for (j=i; jmst.length; j+)if (mstj.weightminweight)minweight = mstj.weight;min = j;/寻找当前最小权值的边的顶点/更新最小权值/保存当前最小权值边的终点序号Edge temp = msti;msti = mstmin; mstmin = temp;/交换最小权值的边u = msti.dest;/刚并入 U 的顶点/调整 msti+1及其后元素为权for (j=i+1; jmst.length; j+

8、)值最小的边v = mstj.dest;if (adjmatrixuvmstj.weight)/原边在 V-U 中的终点/若值更小的边(u,v)，则用(u,v)边替换原边mstj.weight = adjmatrixuv;mstj.start = u;System.out.pr(nmst 数组：); for(j=0; j0)String str=;for(i=0; itable.length-1; i+) str += tablei+,;return str+tabletable.length-1+;return null;public void shortestPath(顶点 v 的单源最短

9、路径v)/以 Dijkstra 算法求带权图中n = this.vertexCount(); dist = newn;/顶点个数/最短路径长度/最短路径的终点的前一个顶path = newn;点 s = newn;/已求出最短路径的顶点集合，初值全为 0sv = 1;/源点在集合 S 中的标记/初始化 dist 和 path 数组for (i=0; in; i+)disti = this.adjmatrixvi;if (i!=v & distiMAX_WEIGHT) pathi = v;elsepathi = -1;System.out.pr System.out.prSystem.out.p

10、r(ns 数组+toString(s); (tpath 数组+toString(path);(tdist 数组+toString(dist);for (i=1; in; i+)径，u 在 V-S 集合中mindist=MAX_WEIGHT, u=0;/寻找从 v 到顶点u 的最短路for (j=0; jn; j+)if (sj=0 & distjmindist)u = j;mindist = distj;/if (mindist=MAX_WEIGHT)/若没有其他最短路径则算法结束；此语句对非连通图是必须的/return;su = 1;/确定一条最短路径的终点 u 并入集合 Sfor (j=0

11、; jn; j+)/调整从v 到V-S 中其他顶点的最短路径及长度if(sj=0 distu+this.adjmatrixujdistj)&this.adjmatrixujMAX_WEIGHT&distj = distu + this.adjmatrixuj;pathj = u;System.out.pr System.out.prSystem.out.pr(ns 数组+toString(s); (tpath 数组+toString(path);(tdist 数组+toString(dist);System.out.prln(n 从顶点+get(v)+到其他顶点的最短路径如下：); i=v+1

12、;while (i!=v)j=i;String pathstr=; while (pathj!=-1)pathstr = ,+get(j)+pathstr; j=pathj;pathstr = (+get(v)+pathstr+)，路径长度为+disti; System.out.prln(pathstr);i = (i+1)%n;/*未实现public联的边removeVertex(E vertex)/删除顶点 vertex 及其关return this.vertexlist.remove(vertex);/删除顺序表中值为vertex 的元素*/public class ShortestPa

13、th短路径public sic void main(String args)/求带权图的单源最String verti=A,B,C,D,E;/带权有向图 G7 的顶点集合Edge edges= new Edge(0,1,10), new/G7 的边集合Edge(0,3,30), new Edge(0,4,99),new Edge(1,2,50),new Edge(2,4,10),new Edge(3,2,20), new Edge(3,4,60); AdjMatrixGraph graph = new AdjMatrixGraph(verti,edges);System.out.prln(带权

14、有向图 G7，+graph.toString();graph.shortestPath(0);/从顶点 A 到其他顶点的最短路径/graph.shortestPath(1);/从顶点B 到其他顶点的最短路径?三、作品操作说明程序运行结果如下：带权有向图 G7，顶点集合：A, B, C, D, E邻接矩阵:0100500203009910600s 数组1,0,0,0,0s 数组1,1,0,0,0s 数组1,1,0,1,0s 数组1,1,1,1,0s 数组1,1,1,1,1path 数组-1,0,-1,0,0 dist 数组0,10,2147483647,30,99path 数组-1,0,1,0,0path 数组-1,0,3,0,3path 数组-1,0,3,0,2path 数组-1,0,3,0,2dist 数组0,10,60,30,99 dist 数组0,10,50,30,90 dist 数组0,10,50,30,60di