【正文】 Edge[v][col] MaxValue ) //無窮大 return col。 return 1。 //無鄰接點(diǎn) } //插入一個(gè)頂點(diǎn) public int InsertVertex ( String vertex ){ if(IsGraphFull()) return 1。 //插入失敗 //頂點(diǎn)表增加一個(gè)元素 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。 //插入位置 } //插入一個(gè)邊 public boolean InsertEdge( int v1, int v2, double weight){ if (v1 0 || v1 CurrentVertices 1) return false。 //出錯(cuò) if (v2 0 || v2 CurrentVertices 1) return false。 Edge[v1][v2]=weight。 //網(wǎng),有向邊 return true。 } //刪除一個(gè)頂點(diǎn) public boolean RemoveVertex ( int v ){ if (v 0 || v CurrentVertices 1) return false。 //出錯(cuò) //修改頂點(diǎn)表 for(int i=v+1。i CurrentVertices。i++) VerticesList[i1]=VerticesList[i]。 //修改鄰接矩陣 int k=0。 //累計(jì)將要?jiǎng)h去的邊數(shù) 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。 //修改頂點(diǎn)數(shù) CurrentEdges=k。 //修改邊數(shù) return true。 } //刪除一個(gè)邊 public boolean RemoveEdge ( int v1, int v2 ){ if (v1 0 || v1 CurrentVertices 1) return false。 //用1表示出錯(cuò) if (v2 0 || v2 CurrentVertices 1) return false。 if ( v1==v2) return false。 Edge[v1][v2]=MaxValue。 //網(wǎng),無路徑 return true。 } //打印鄰接矩陣 public void display(){ int i,j。 ( 頂點(diǎn)表)。 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表示還未求出最短路徑 */ /* 一開始假定取直達(dá)路徑最短 */ dist[v]=Edge[v0][v]。 /* 直達(dá)情況下的最后經(jīng)由點(diǎn)就是出發(fā)點(diǎn) */ if(dist[v]MaxValueamp。amp。v!=v0) path[v]=v0。 else path[v]=1。 /* 無直達(dá)路徑 */ } /*初始時(shí)源點(diǎn)v0∈S集，表示v0到v0的最短路徑已經(jīng)找到*/ dist[v0]=0。s[v0]=1。 //下來假設(shè)經(jīng)由一個(gè)點(diǎn)中轉(zhuǎn)到達(dá)其余各點(diǎn),會(huì)近些,驗(yàn)證之. //再假設(shè)經(jīng)由兩個(gè)點(diǎn)中轉(zhuǎn),會(huì)更近些,驗(yàn)證之,..... //直到窮舉完所有可能的中轉(zhuǎn)點(diǎn). double min。 for(i=1。iCurrentVertices 。i++) { //挑一個(gè)距離最近經(jīng)由點(diǎn),下標(biāo)裝入v min=MaxValue。 for(w=0。wCurrentVertices。w++) /*頂點(diǎn)w不屬于S集且離v0更近*/ if(s[w]==0 amp。amp。 dist[w]min){ v=w。 /* 經(jīng)由頂點(diǎn)w中轉(zhuǎn)則距離更短 */ min=dist[w]。 } s[v]=1。 /*頂點(diǎn)v并入S， 由v0到達(dá)v頂點(diǎn)的最短路徑為min*/ /*假定由v0到v，再由v直達(dá)其余各點(diǎn)， 更新當(dāng)前最后一個(gè)經(jīng)由點(diǎn)及距離*/ for(j=0。jCurrentVertices。j++) if(s[j]==0 amp。amp。 (min+Edge[v][j]dist[j])){ /* 如果多經(jīng)由一個(gè)v點(diǎn)到達(dá)j點(diǎn)的 最短路徑反而要短,就更新.*/ dist[j]=min+Edge[v][j]。 path[j]=v。 /* 經(jīng)由點(diǎn)的序號(hào) */ }/*if*/ }/*循環(huán)for i */ }/*Dijkstra算法結(jié)束*/ //輸出Dijkstra算法的結(jié)果 public String Putpath(int v0,int vj) { String t=,T=。 int i=vj,next。 //for(i=0。iCurrentVertices。i++) /* v0到各點(diǎn)的路徑 */ if(dist[i]MaxValue amp。amp。 i!=v0){ /* 如果有路徑 */ (VerticesList[i]+)。 /* 終點(diǎn) */ next=path[i]。 /* 第一個(gè)經(jīng)由點(diǎn) */ while(next!=v0){ //(VerticesList[next]+)。 t+=VerticesList[next]+。 next=path[next]。 /* 下一個(gè)經(jīng)由點(diǎn) */ } /* 起點(diǎn)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。 }/*結(jié)束Putpath*/ //主函數(shù) public static void main(String []args){ GraphPath G=new GraphPath()。 //鄰接矩陣 //準(zhǔn)備有向圖（網(wǎng)）數(shù)據(jù) String c[]={01,02,03,04,05,06,07,08,09,10,11}。 //頂點(diǎn) 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 }。 //權(quán) //插入頂點(diǎn) for(int i=0。i11。i++) (c[i])。 //插入弧 for(int i=0。i32。i++) (v[i][0],v[i][1],e[i])。 //打印輸出 //()。 /* 圖的鄰接矩陣已經(jīng)建好 */ //求從0點(diǎn)到其余各點(diǎn)的最短路徑 (0)。 // (0,1)。 //輸出結(jié)果 ((0,1))。 } //main方法結(jié)束} //“鄰接矩陣”類結(jié)