package com.doumee.core.utils; import java.util.*; /** * 最短路径—Dijkstra算法和Floyd算法 * Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。注意该算法要求图中不存在负权边。 * * 问题描述:在无向图 G=(V,E) 中,假设每条边 E[i] 的长度为 w[i],找到由顶点 V0 到其余各点的最短路径。(单源最短路径) */ public class GraphByMatrix { public static final boolean UNDIRECTED_GRAPH = false;//无向图标志 public static final boolean DIRECTED_GRAPH = true;//有向图标志 public static final boolean ADJACENCY_MATRIX = true;//邻接矩阵实现 public static final boolean ADJACENCY_LIST = false;//邻接表实现 public static final int MAX_VALUE = Integer.MAX_VALUE; private boolean graphType; private boolean method; private int vertexSize; private int matrixMaxVertex; //存储所有顶点信息的一维数组 private Object[] vertexesArray; //存储图中顶点之间关联关系的二维数组,及边的关系 private int[][] edgesMatrix; // 记录第i个节点是否被访问过 private boolean[] visited; /** * @param graphType 图的类型:有向图/无向图 * @param method 图的实现方式:邻接矩阵/邻接表 */ public GraphByMatrix(boolean graphType, boolean method, int size) { this.graphType = graphType; this.method = method; this.vertexSize = 0; this.matrixMaxVertex = size; if (this.method) { visited = new boolean[matrixMaxVertex]; vertexesArray = new Object[matrixMaxVertex]; edgesMatrix = new int[matrixMaxVertex][matrixMaxVertex]; //对数组进行初始化,顶点间没有边关联的值为Integer类型的最大值 for (int row = 0; row < edgesMatrix.length; row++) { for (int column = 0; column < edgesMatrix.length; column++) { edgesMatrix[row][column] = MAX_VALUE; } } } } /********************最短路径****************************/ //计算一个顶点到其它一个顶点的最短距离 public void Dijkstra(Object obj) throws Exception { Dijkstra(getVertexIndex(obj)); } public void Dijkstra(int v0) { int[] dist = new int[matrixMaxVertex]; int[] prev = new int[matrixMaxVertex]; //初始化visited、dist和path for (int i = 0; i < vertexSize; i++) { //一开始假定取直达路径最短 dist[i] = edgesMatrix[v0][i]; visited[i] = false; //直达情况下的最后经由点就是出发点 if (i != v0 && dist[i] < MAX_VALUE) prev[i] = v0; else prev[i] = -1; //无直达路径 } //初始时源点v0∈visited集,表示v0 到v0的最短路径已经找到 visited[v0] = true; // 下来假设经由一个点中转到达其余各点,会近些,验证之 // 再假设经由两个点中转,会更近些,验证之,..... // 直到穷举完所有可能的中转点 int minDist; int v = 0; for (int i = 1; i < vertexSize; i++) { //挑一个距离最近经由点,下标装入 v minDist = MAX_VALUE; for (int j = 0; j < vertexSize; j++) { if ((!visited[j]) && dist[j] < minDist) { v = j; // 经由顶点j中转则距离更短 minDist = dist[j]; } } visited[v] = true; /*顶点v并入S,由v0到达v顶点的最短路径为min. 假定由v0到v,再由v直达其余各点,更新当前最后一个经由点及距离*/ for (int j = 0; j < vertexSize; j++) { if ((!visited[j]) && edgesMatrix[v][j] < MAX_VALUE) { if (minDist + edgesMatrix[v][j] <= dist[j]) { //如果多经由一个v点到达j点的 最短路径反而要短,就更新 dist[j] = minDist + edgesMatrix[v][j]; prev[j] = v; //经由点的序号 } } } } for (int i = 1; i < matrixMaxVertex; i++) { System.out.println("**" + vertexesArray[v0] + "-->" +vertexesArray[i] + " 的最短路径是:" + dist[i]); } } //获取顶点值在数组里对应的索引 private int getVertexIndex(Object obj) throws Exception { int index = -1; for (int i = 0; i < vertexSize; i++) { if (vertexesArray[i].equals(obj)) { index = i; break; } } if (index == -1) { throw new Exception("没有这个值!"); } return index; } /** * 单源最短路径算法,用于计算一个节点到其他!!所有节点!!的最短路径 */ public void Dijkstra2(int v0) { // LinkedList实现了Queue接口 FIFO Queue queue = new LinkedList<>(); for (int i = 0; i < vertexSize; i++) { visited[i] = false; } List> result = new ArrayList<>(); //这个循环是为了确保每个顶点都被遍历到 int lastRow =0; for (int i = 0; i < vertexSize; i++) { if (!visited[i]) { queue.add(i); visited[i] = true; while (!queue.isEmpty()) { int row = queue.remove(); Map map = new HashMap<>(); map.put("name", vertexesArray[row]); map.put("row", row); int tempDis =0; if(row>0){ tempDis = edgesMatrix[lastRow][row]; lastRow =row; } map.put("dis", tempDis); result.add(map); System.out.print(vertexesArray[row] + "-->"); for (int k = getMin(row); k >= 0; k = getMin(row)) { if (!visited[k]) { queue.add(k); visited[k] = true; } } } } } System.out.println(""); int totalDis =0; for(Map c :result){ totalDis += (Integer) c.get("dis"); System.out.print( c.get("name") + "--"+c.get("dis")+"-->"); } System.out.println(""); System.out.println("最短距离"+totalDis); } private int getMin( int row) { int minDist = MAX_VALUE; int index = 0; for (int j = 0; j < vertexSize; j++) { if ((!visited[j]) && edgesMatrix[row][j] < minDist) { minDist = edgesMatrix[row][j]; index = j; } } if (index == 0) { return -1; } return index; } public boolean addVertex(Object val) { assert (val != null); vertexesArray[vertexSize] = val; vertexSize++; return true; } public boolean addEdge(int vnum1, int vnum2, int weight) { assert (vnum1 >= 0 && vnum2 >= 0 && vnum1 != vnum2 && weight >= 0); //有向图 if (graphType) { edgesMatrix[vnum1][vnum2] = weight; } else { edgesMatrix[vnum1][vnum2] = weight; edgesMatrix[vnum2][vnum1] = weight; } return true; } public static void main(String[] args) throws Exception { GraphByMatrix graph = new GraphByMatrix(GraphByMatrix.DIRECTED_GRAPH, GraphByMatrix.ADJACENCY_MATRIX, 9); graph.addVertex("A");//0 graph.addVertex("B");//1 graph.addVertex("C");//2 graph.addVertex("D");//3 graph.addVertex("E");//4 //A->B、C、D graph.addEdge(0, 1,10); graph.addEdge(0, 2,5); graph.addEdge(0, 3,7); //B->C、D、E graph.addEdge(1, 2,4); graph.addEdge(1, 3,5); graph.addEdge(1, 4,10); //C->B、D、E graph.addEdge(2, 1,4); graph.addEdge(2, 3,6); graph.addEdge(2, 4,5); //D->B、C、E graph.addEdge(3, 1,5); graph.addEdge(3, 2,6); graph.addEdge(3, 4,7); graph.Dijkstra(0); System.out.println(); graph.Dijkstra("C"); System.out.println(); graph.Dijkstra2(0); System.out.println(); } }