【正文】 return 1。 //用 1表示出錯 //鄰接矩陣的行號和列號是兩個鄰接點的序號 for ( int col = 0。 col CurrentVertices。 col++ ) if ( Edge[v][col] 0 amp。amp。 //自身 Edge[v][col] MaxValue ) //無窮大 return col。 return 1。 //無鄰接點 } //插入一個頂點 public int InsertVertex ( String vertex ){ if(IsGraphFull()) return 1。 //插入失敗 //頂點表增加一個元素 VerticesList[CurrentVertices]=vertex。 //鄰接矩陣增加一行一列 for ( int j = 0。j =CurrentVertices。j++ ) { Edge[CurrentEdges][j]=MaxValue。 Edge[j][CurrentEdges]=MaxValue。 } Edge[CurrentEdges][CurrentEdges]=0。 CurrentVertices++。 return CurrentVertices。 //插入位置 } //插入一個邊 public boolean InsertEdge( int v1, int v2, double weight){ if (v1 0 || v1 CurrentVertices 1) return false。 //出錯 if (v2 0 || v2 CurrentVertices 1) return false。 Edge[v1][v2]=weight。 //網 ,有向邊 return true。 } //刪除一個頂點 public boolean RemoveVertex ( int v ){ if (v 0 || v CurrentVertices 1) return false。 //出錯 //修改頂點表 for(int i=v+1。i CurrentVertices。i++) VerticesList[i1]=VerticesList[i]。 //修改鄰接矩陣 int k=0。 //累計將要刪去的邊數 for(int i=0。i CurrentVertices。i++) if ( Edge[v][i] 0 amp。amp。 //自身 Edge[v][i] MaxValue ) //無窮大 k++。 //第 v行 for(int i=0。i CurrentVertices。i++) if ( Edge[i][v] 0 amp。amp。 //自身 Edge[i][v] MaxValue ) //無窮大 k++。 //第 v列 //覆蓋第 v行 int j。 for(int i=v+1。i CurrentVertices。i++) for(j=0。j CurrentVertices。j++) Edge[i1][j]=Edge[i][j]。 //覆蓋第 v列 for(j=v+1。j CurrentVertices。j++) for(int i=0。i CurrentVertices。i++) Edge[i][j1]=Edge[i][j]。 CurrentVertices。 //修改頂點數 CurrentEdges=k。 //修改邊數 return true。 } //刪除一個邊 public boolean RemoveEdge ( int v1, int v2 ){ if (v1 0 || v1 CurrentVertices 1) return false。 //用 1表示出錯 if (v2 0 || v2 CurrentVertices 1) return false。 if ( v1==v2) return false。 Edge[v1][v2]=MaxValue。 //網 ,無路徑 return true。 } //打印鄰接矩陣 public void display(){ int i,j。 ( 頂點表 )。 for(i=0。iCurrentVertices。i++) (VerticesList[i]+ )。 (39。\n39。+ 鄰接矩陣 )。 for(i=0。iCurrentVertices。i++) { for(j=0。jCurrentVertices。j++) if(Edge[i][j]==MaxValue) (39。@39。+ )。 else (Edge[i][j]+ )。 ()。 } } //最短路徑的 ijkstra算法 : public void Dijkstra(int v0) { int s[]=new int[MaxVertices]。 int v,i,j,w。 /*初始化 s、 dist和 path*/ for(v=0。 vCurrentVertices。 v++){ s[v]=0。 /* 0表示還未求出最短路徑 */ /* 一開始假定取直達路徑最短 */ dist[v]=Edge[v0][v]。 /* 直達情況下的最后經由點就是出發(fā)點 */ if(dist[v]MaxValueamp。amp。v!=v0) path[v]=v0。 else path[v]=1。 /* 無直達路徑 */ } /*初始時源點 v0∈ S集，表示 v0到 v0的最短路徑已經找到 */ dist[v0]=0。s[v0]=1。 //下來假設經由一個點中轉到達其余各點 ,會近些 ,驗證之 . //再假設經由兩個點中轉 ,會更近些 ,驗證之 ,..... //直到窮舉完所有可能的中轉點 . double min。 for(i=1。iCurrentVertices 。i++) { //挑一個距離最近經由點 ,下標裝入 v min=MaxValue。 for(w=0。wCurrentVertices。w++) /*頂點 w不屬于 S集且離 v0更近 */ if(s[w]==0 amp。amp。 dist[w]min){ v=w。 /* 經由頂點 w中轉則距離更短 */ min=dist[w]。 } s[v]=1。 /*頂點 v并入 S， 由 v0到達 v頂點的最短路徑為 min*/ /*假定由 v0到 v，再由 v直達其余各點， 更新當前最后一個經由點及距離 */ for(j=0。jCurrentVertices。j++) if(s[j]==0 amp。amp。 (min+Edge[v][j]dist[j])){ /* 如果 多經由一個 v點到達 j點的 最短路徑反而要短 ,就更新 .*/ dist[j]=min+Edge[v][j]。 path[j]=v。 /* 經由點的序號 */ }/*if*/ }/*循環(huán) for i */ }/*Dijkstra算法結束 */ //輸出 Dijkstra算法的結果 public String Putpath(int v0,int vj) { String t=,T=。 int i=vj,next。 //for(i=0。iCurrentVertices。i++) /* v0到各點的路徑 */ if(dist[i]MaxValue amp。amp。 i!=v0){ /* 如果有路徑 */ (VerticesList[i]+)。 /* 終點 */ next=path[i]。 /* 第一個經由點 */ while(next!=v0){ //(VerticesList[next]+)。 t+=VerticesList[next]+。 next=path[next]。 /* 下一個經由點 */ } /* 起點 v0和最短路徑值 */ //(VerticesList[v0]+:+dist[i])。 t+=VerticesList[v0]+:+dist[i]。 //(t)。 T=t。 } else if(i!=v0) { /* 無路徑 */ (VerticesList[i]+ +VerticesList[v0]+:no path\n)。 t=VerticesList[i]+ +VerticesList[v0]+:no path\n。 } return T。 }/*結束 Putpath*/ //主函數 public static void main(String []args){ GraphPath G=new GraphPath()。 //鄰接矩陣 //準備有向圖（網）數據 String c[]={01,02,03,04,05,06,07,08,09,10,11}。 //頂點 int v[][]={ //弧 {0,1},{0,2},{1,0},{1,2},{1,8},{1,10},{2,0},{2,1},{2,3},{2,4}, {3,2},{3,5},{3,6},{4,2},{4,5},{5,3},{5,4},{5,6},{5,8},{5,10}, {6,3},{6,5},{6,7},{7,6},{8,1},{8,5},{8,9},{8,10},{9,8},{10,1}, {10,5},{10,8} }。 double e[]={15,10,15,10,130,280,10,10,80,100,80,150,250,100,20, 150,20,100,300,150,250,100,200,200,130,300, 100,100,100,280,150,100 }。 //權 //插入頂點 for(int i=0。i11。i++) (c[i])。 //插入弧 for(int i=0。i32。i++) (v[i][0],v[i][1],e[i])。 //打印輸出 //()。 /* 圖的鄰接矩陣已經建好 */ //求從 0點到其余各點的最短路徑 (0)。 // (0,1)。 //輸出結果 ((0,1))。 } //main方法結束 } //“鄰接矩陣”類結束