过去的代码有些地方现在看来有些怪怪的，例如MGraph里面public的成员变量。
没有提现java的封装的思想。
另外，添加必要非空判断。否则参数传null必定报错。
entity:
/** * @author 无名 * @Description:邻接矩阵 * @date 2015-12-29 上午10:02:16 */ public class MGraph { // 顶点为空 public static final int NULL = 1000; // 邻接矩阵 private int[][] edges = new int[9][9]; // 顶点数和边数 private int n, e; public int[][] getEdges() { return edges; } public void setEdges(int[][] edges) { this.edges = edges; } public int getN() { return n; } public void setN(int n) { this.n = n; } public int getE() { return e; } public void setE(int e) { this.e = e; }
图操作，及求最短路径代码：
package com.alg.utils; import com.entity.MGraph; /** * @author 无名 * @date 2014年，2015-12-29 上午10:09:17修改,entity提现java封装思想，加入get，set； * 方法添加非空判断。 * @Description: 邻接矩阵基本操作 */ public class MgraphUtils { // 根据二维数组，生成邻接矩 public static void createMat(MGraph g, int A[][], int n) { if(null == A||null == g) return; int e = 0; int[][] edges = new int[9][9]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { edges[i][j] = A[i][j]; if (edges[i][j] != MGraph.NULL) e++; } g.setN(n); g.setEdges(edges); g.setE(e); } // 输出邻接矩阵 public static void DispMat(MGraph g) { if(null == g) return; int i, j,n=g.getN(); int[][] edges = g.getEdges(); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if (edges[i][j] == MGraph.NULL) System.out.print("-" + " "); else System.out.print(edges[i][j] + " "); } System.out.println(); } } // Dijkstra算法 public static void Dijkstra(MGraph mgraph, int v0) { if(null == mgraph) return; final int INFINITY = 65535; // 用于存储最短路径下标数组 int[] pathMatirx = new int[9]; // 用于存储到各点最短路径权值 int[] shortPathTable = new int[9]; int min, v, w, k = 0; // finalGot[n] = 1表示求得v0 - vn最短路径 int[] finalGot = new int[9]; int mgraphN = mgraph.getN(); int[][] mgraphEdges = mgraph.getEdges(); // 初始化数据 for (v = 0; v < mgraphN; v++) { // 全部顶点初始化为未知最短路径状态 finalGot[v] = 0; // 将与与v0有连线的点加上权值 shortPathTable[v] = mgraphEdges[v0][v]; // 初始化路径数组为0 pathMatirx[v] = 0; } // v0至v0路径为0 shortPathTable[v0] = 0; // v0至v0不须求路径 finalGot[v0] = 1; for (v = 1; v < mgraph.getN(); v++) { min = INFINITY; // 寻找距v0最近顶点 for (w = 0; w < mgraphN; w++) { if (finalGot[w] == 0 && shortPathTable[w] < min) { k = w; min = shortPathTable[w]; } } // 将找到的顶点标记为1 finalGot[k] = 1; // 修正当前最短路径及距离 for (w = 0; w < mgraphN; w++) { // 如果经过v顶点的路径比现在这条路径距离短的话 if (finalGot[w] == 0 && (min + mgraphEdges[k][w] < shortPathTable[w])) { shortPathTable[w] = min + mgraphEdges[k][w]; pathMatirx[w] = k; } } } // 输出 System.out.println("Dijkstra算法求得最短路径: "); for (v = 1; v < mgraphN; v++) { k = v; System.out.print(k + "->"); while (k != v0) { k = pathMatirx[k]; System.out.print(k + "->"); } System.out.println(); } } // 弗洛伊德算法基本思想与Dijkstra算法相似 public static void Floyd(MGraph mgraph) { if(null == mgraph) return; int[][] shortPathTable = new int[9][9]; int[][] pathMatirx = new int[9][9]; int mgraphN = mgraph.getN(); int[][] mgraphEdges = mgraph.getEdges(); int v, w, k; for (v = 0; v < mgraphN; v++) { for (w = 0; w < mgraphN; w++) { shortPathTable[v][w] = mgraphEdges[v][w]; pathMatirx[v][w] = w; } } for (k = 0; k < mgraphN; k++) { for (v = 0; v < mgraphN; v++) { for (w = 0; w < mgraphN; w++) { if (shortPathTable[v][w] > shortPathTable[v][k] + shortPathTable[k][w]) { shortPathTable[v][w] = shortPathTable[v][k] + shortPathTable[k][w]; pathMatirx[v][w] = pathMatirx[v][k]; } } } } // 显示 System.out.println("Floyd算法求得最短路径："); for (v = 0; v < mgraphN; v++) { for (w = v + 1; w < mgraphN; w++) { System.out.print("v" + v + "->v" + w + "weight:" + shortPathTable[v][w] + " "); k = pathMatirx[v][w]; System.out.print("path:" + v); while (k != w) { System.out.print("->" + k); k = pathMatirx[k][w]; } System.out.println("->" + w); } System.out.println(); } } }
测试代码：
package com.test; import com.alg.utils.MgraphUtils; import com.entity.MGraph; public class TestGraph { public static void main(String[] args) { MGraph mg = new MGraph(); int[][] array = new int[9][9]; for(int i = 0;i < 9; i++) for(int j = 0;j < 9; j++) array[i][j] = MGraph.NULL; array[0][1] = 1; array[1][0] = 1; array[0][2] = 5; array[2][0] = 5; array[1][2] = 3; array[2][1] = 3; array[1][3] = 7; array[3][1] = 7; array[3][4] = 2; array[4][3] = 2; array[1][4] = 5; array[4][1] = 5; array[2][4] = 1; array[4][2] = 1; array[2][5] = 7; array[5][2] = 7; array[4][5] = 3; array[5][4] = 3; array[3][6] = 3; array[6][3] = 3; array[4][6] = 6; array[6][4] = 6; array[4][7] = 9; array[7][4] = 9; array[5][7] = 5; array[7][5] = 5; array[6][7] = 2; array[7][6] = 2; array[6][8] = 7; array[8][6] = 7; array[7][8] = 4; array[8][7] = 4; MgraphUtils.createMat(mg, array, 9); MgraphUtils.DispMat(mg); MgraphUtils.Dijkstra(mg, 0); MgraphUtils.Floyd(mg); } }