學(xué)生作品-帶權(quán)圖的單源最短路徑問題說明

1、一、作品要求編寫求帶權(quán)圖的單源最短路徑程序。二、學(xué)生作品分析1、代碼分析代碼分析如下：public class AdjMatrixGraph extends AbstractGraph類，繼承抽象圖類/鄰接矩陣表示的圖protected SeqList vertexlist;/順序表圖的頂點集合protectedprivate final adjmatrix;MAX_WEIGHT =/圖的鄰接矩陣eger.MAX_VALUE; /最大權(quán)值（表示無窮大）/privateedgeCount;/邊數(shù)?public AdjMatrixGraph(n)/構(gòu)造方法，n 指定最多頂點數(shù)this.vertex

2、list = new SeqList(n);/構(gòu)造指定容量的空順序表/構(gòu)造 n 行 n 列空矩陣/初始化圖的鄰接矩陣this.adjmatrix = newnn;for (i=0; in; i+)for (j=0; jn; j+)this.adjmatrixij= (i=j) ? 0 : MAX_WEIGHT;/邊的權(quán)值為 0 或最大權(quán)值/this.edgeCount=0;public AdjMatrixGraph(E verti, Edge edges) /以頂點集合和邊集合構(gòu)造一個圖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) /以頂點集合和邊集合構(gòu)造一個圖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;/頂點數(shù)for (i=0; in; i+)for(j=0; j=0 & i=0 & j=0 & vn

5、)this.vertexlist.remove(v);/刪除順序表的第 i 個元素，頂點數(shù)已減一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()姆算法/構(gòu)造

6、帶權(quán)圖最小生成樹的/返回最小生成樹相應(yīng)的圖對象Edge mst = new EdgevertexCount()-1;/n 個頂點最小生成樹有n-1條邊f(xié)or (i=0; imst.length; i+)發(fā)構(gòu)造最小生成樹/初始化 mst 數(shù)組，從頂點 v0 出msti = new Edge(0, i+1, adjmatrix0i+1);/保存從頂點 v0 到其他各頂點的邊的權(quán)System.out.pr(mst 數(shù)組初值：); for(j=0; jmst.length; j+)System.out.pr(mstj.toString();/顯示 mst 數(shù)組的變化過程for (i=0; imst.l

7、ength; i+)/共選出 n-1 條邊minweight = MAX_WEIGHT;min = i;/求最小權(quán)值for (j=i; jmst.length; j+)if (mstj.weightminweight)minweight = mstj.weight;min = j;/尋找當(dāng)前最小權(quán)值的邊的頂點/更新最小權(quán)值/保存當(dāng)前最小權(quán)值邊的終點序號Edge temp = msti;msti = mstmin; mstmin = temp;/交換最小權(quán)值的邊u = msti.dest;/剛并入 U 的頂點/調(diào)整 msti+1及其后元素為權(quán)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 數(shù)組：); 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 算法求帶權(quán)圖中n = this.vertexCount(); dist = newn;/頂點個數(shù)/最短路徑長度/最短路徑的終點的前一個頂path = newn;點 s = newn;/已求出最短路徑的頂點集合，初值全為 0sv = 1;/源點在集合 S 中的標(biāo)記/初始化 dist 和 path 數(shù)組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 數(shù)組+toString(s); (tpath 數(shù)組+toString(path);(tdist 數(shù)組+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)/若沒有其他最短路徑則算法結(jié)束；此語句對非連通圖是必須的/return;su = 1;/確定一條最短路徑的終點 u 并入集合 Sfor (j=0

11、; jn; j+)/調(diào)整從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 數(shù)組+toString(s); (tpath 數(shù)組+toString(path);(tdist 數(shù)組+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;/*未實現(xiàn)public聯(lián)的邊removeVertex(E vertex)/刪除頂點 vertex 及其關(guān)return this.vertexlist.remove(vertex);/刪除順序表中值為vertex 的元素*/public class ShortestPa

13、th短路徑public sic void main(String args)/求帶權(quán)圖的單源最String verti=A,B,C,D,E;/帶權(quán)有向圖 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(帶權(quán)

14、有向圖 G7，+graph.toString();graph.shortestPath(0);/從頂點 A 到其他頂點的最短路徑/graph.shortestPath(1);/從頂點B 到其他頂點的最短路徑?三、作品操作說明程序運行結(jié)果如下：帶權(quán)有向圖 G7，頂點集合：A, B, C, D, E鄰接矩陣:0100500203009910600s 數(shù)組1,0,0,0,0s 數(shù)組1,1,0,0,0s 數(shù)組1,1,0,1,0s 數(shù)組1,1,1,1,0s 數(shù)組1,1,1,1,1path 數(shù)組-1,0,-1,0,0 dist 數(shù)組0,10,2147483647,30,99path 數(shù)組-1,0,1,0,0path 數(shù)組-1,0,3,0,3path 數(shù)組-1,0,3,0,2path 數(shù)組-1,0,3,0,2dist 數(shù)組0,10,60,30,99 dist 數(shù)組0,10,50,30,90 dist 數(shù)組0,10,50,30,60di