狄克斯特拉算法(Dijkstra)：从一个点到其余各结点的最短路径。
算法说明：
从一个点到其余各结点的最短路径。
设置两个结点的集合S和T，集合S中存放已找到最短路径的结点，集合T中存放当前还未找到最短路径的结点。初始状态时，集合S中只包含源点，设为v0，然后从集合T中选择到源点v0路径长度最短的结点u加入到集合S中，集合S中每加入一个新的结点u都要修改源点v0到集合T中剩余结点的当前最短路径长度值，集合T中各结点的新的当前最短路径长度值，为原来的当前最短路径长度值与从源点过结点u到达该结点的路径长度中的较小者。此过程不断重复，直到集合T中的结点全部加入到集合S 中为止。 下图为意示例：所用的邻接矩阵与前一篇的一样，weight类和visit类也一样
public class Dijkstra { static final int maxWeight = 9999; //distance保存了从起始节点到每一个节点的最短距离 //path保存了路径 //v0是起始节点 public static void dijkstra(MyAdjGraphic g,int v0,int[] distance,int[] path) throws Exception { int n = g.getNumOfVertice();//结点数量 int[] s = new int[n]; //标示结点是否已被访问的数组 int minDis; //每次找到的最短路径 int u=0; //下一次最短路径对应的结点的下标 //初始化，把初始节点距离所有节点的信息初始化 for(int i=0;i 测试类：
public class Test { static final int maxVertices = 100; public static void main(String[] args) { MyAdjGraphic g = new MyAdjGraphic(maxVertices); Object[] vertices = {new Character('A'),new Character('B'),new Character('C'), new Character('D'),new Character('E'),new Character('F')}; Weight[] weight = {new Weight(0,2,5),new Weight(0,3,30),new Weight(1,0,2), new Weight(1,4,8),new Weight(2,1,15),new Weight(2,5,7),new Weight(4,3,4), new Weight(5,3,10),new Weight(5,4,18)}; int n = 6; int e = 9; try { Weight.createAdjGraphic(g, vertices, n, weight, e); int[] distance = new int[n]; int[] path = new int[n]; Dijkstra.dijkstra(g, 0, distance, path); System.out.println("从顶点A到其他各顶点的最短距离为："); for(int i = 1; i < n; i ++) { System.out.println("到顶点" + g.getValueOfVertice(i) + "的最短距离为：" + distance[i]); } System.out.println("从顶点A到其他各顶点的前一顶点分别为："); for(int i = 0; i < n; i ++) { if(path[i] != -1) { System.out.println("到顶点" + g.getValueOfVertice(i) + "的前一顶点为：" + g.getValueOfVertice(path[i])); } } } catch(Exception ex) { ex.printStackTrace(); } }}
弗洛伊德算法(Floyd)：每对结点之间的最短路径
算法思想：
每对结点之间的最短路径。
设矩阵cost用来存放带权有向图G的权值，即矩阵元素cost[i][j]中存放着下标为i的结点到下标为j的结点之间的权值，可以通过递推构造一个矩阵序列A0,A1,A2,……,AN来求每对结点之间的最短路径。初始时有，A0[i][j]=cost[i][j]。当已经求出Ak,要递推求解Ak+1时，可分两种情况来考虑：一种情况是该路径不经过下标为k+1的结点，此时该路径长度与从结点vi到结点vj的路径上所经过的结点下标不大于k的最短路径长度相同；另一种情况是该路径经过下标为k+1的结点，此时该路径可分为两段，一段是从结点vi到结点vk+1的最短路径，另一段是从结点vk+1到结点vj的最短路径，此时的最短路径长度等于这两段最短路径长度之和。这两种情况中的路径长度较小者，就是要求的从结点vi到结点vj的路径上所经过的结点下标不大于k+1的最短路径长度。//佛洛依德算法类public class Floyd { int[][] length = null;// 任意两点之间路径长度 int[][][] path = null;// 任意两点之间的路径 public Floyd(int[][] G) { //不联通的两节点默认为之间的权值很大，设为MAX int MAX = 100; int row = G.length;// 图G的行数 int[][] spot = new int[row][row];// 定义任意两点之间经过的点 int[] onePath = new int[row];// 记录一条路径 length = new int[row][row]; path = new int[row][row][]; //处理任意两点之间的权值，不联通的节点设置为很大的值 for (int i = 0; i < row; i++) { // 处理图两点之间的路径 for (int j = 0; j < row; j++) { if (G[i][j] == 0||G[i][j] == -1) { G[i][j] = MAX;// 没有路径的两个点之间的路径为默认最大 } if (i == j) { G[i][j] = 0;// 本身的路径长度为0 } } } for (int i = 0; i < row; i++) { // 初始化为任意两点之间没有路径 for (int j = 0; j < row; j++) { spot[i][j] = -1; } } for (int i = 0; i < row; i++) { // 假设任意两点之间的没有路径 onePath[i] = -1; } //初始把处理后的矩阵放在length数组中 for (int v = 0; v < row; ++v) { for (int w = 0; w < row; ++w) { length[v][w] = G[v][w]; } } for (int u = 0; u < row; ++u) { for (int v = 0; v < row; ++v) { for (int w = 0; w < row; ++w) { if (length[v][w] > length[v][u] + length[u][w]) { length[v][w] = length[v][u] + length[u][w];// 如果存在更短路径则取更短路径 spot[v][w] = u;// 把经过的点加入 } } } } for (int i = 0; i < row; i++) { // 求出所有的路径 int[] point = new int[1]; for (int j = 0; j < row; j++) { point[0] = 0; onePath[point[0]++] = i; outputPath(spot, i, j, onePath, point); path[i][j] = new int[point[0]]; for (int s = 0; s < point[0]; s++) path[i][j][s] = onePath[s]; } } } void outputPath(int[][] spot, int i, int j, int[] onePath, int[] point) { // 输出i // 到j // 的路径的实际代码，point[]记录一条路径的长度 if (i == j) { return; } if (spot[i][j] == -1) { onePath[point[0]++] = j; } // System.out.print(" "+j+" "); else { outputPath(spot, i, spot[i][j], onePath, point); outputPath(spot, spot[i][j], j, onePath, point); } } public static void main(String[] args) { int data[][] = { { 0, 2, 3, 6}, { 2, 0, 7, -1}, { 3, 7, 0, 1}, { 6, -1, 1, 0}, }; for (int i = 0; i < data.length; i++) { for (int j = i; j < data.length; j++) { if (data[i][j] != data[j][i]) { return; } } } Floyd test = new Floyd(data); for (int i = 0; i < data.length; i++) { for (int j = i; j < data[i].length; j++) { System.out.println(); System.out.print("From " + (char)(i+65) + " to " + (char)(j+65) + " path is: "); for (int k = 0; k < test.path[i][j].length; k++) { System.out.print(test.path[i][j][k] + " "); } System.out.println(); System.out.println("From " + (char)(i+65) + " to " + (char)(j+65) + " length :" + test.length[i][j]); } } }}