一、简介
迪克斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止，就像剥洋葱一样，所以它也属于广度优先搜索。
二、算法正确性证明
老哥们自己找吧，网上没找到一篇能让我完全满意的证明
三、JAVA代码实现
public class Dijkstra { public static final int INF = 65535; public static final String RIGHT_ARROW = "-->"; public static final String LEFT_ARROW = "<--"; public static void main(String[] args) { getShortestDistance(new int[][]{ {0, INF, 10, INF, 30, 100}, {INF, 0, 5, INF, INF, INF}, {INF, INF, 0, 50, INF, INF}, {INF, INF, INF, 0, INF, 10}, {INF, INF, INF, 20, 0, 60}, {INF, INF, INF, INF, INF, 0} }, 0); } private static void getShortestDistance(int[][] matrix, int start) { boolean[] visited = new boolean[matrix.length]; // 节点是否已被访问 int[] distance = new int[matrix.length]; // 距离数组 int[] pre = new int[matrix.length]; // 前驱数组，用于记录路径信息 // 初始化距离数组、前驱数组，访问数组 for (int j = 0; j < matrix[start].length; j++) { distance[j] = matrix[start][j]; if (distance[j] == INF) { pre[j] = -1; } else { pre[j] = start; } visited[j] = false; } // 初始节点设置为已访问 visited[start] = true; int k = start; while (k != -1) { visited[k] = true; for (int j = 0; j < matrix[k].length; j++) { if (matrix[k][j] + distance[k] < distance[j]) { distance[j] = matrix[k][j] + distance[k]; pre[j] = k; } } // 获取下一个距离起始节点最近的未被访问的节点 k = getNextNodeIndex(visited, distance); } // 打印最短距离和路径 printShortestPath(distance, pre, start); } private static void printShortestPath(int[] distance, int[] pre, int start) { for (int i = 0; i < distance.length; i++) { StringBuilder sb = new StringBuilder(); sb.append(getNodeName(start)); sb.append(RIGHT_ARROW); sb.append(getNodeName(i)); if (distance[i] < INF) { sb.append("最短距离:"); sb.append(distance[i]); sb.append("\t"); } else { sb.append("不通"); continue; } sb.append("最短路径"); sb.append(getNodeName(i)); sb.append(LEFT_ARROW); int j = i; do { j = pre[j]; sb.append(getNodeName(j)); sb.append(LEFT_ARROW); } while (pre[j] != -1 && j != start); System.out.println(sb.substring(0, sb.lastIndexOf(LEFT_ARROW))); } } private static int getNextNodeIndex(boolean[] visited, int[] distance) { int min = INF; int k = -1; for (int i = 0; i < distance.length; i++) { if (distance[i] < min && !visited[i]) { min = distance[i]; k = i; } } return k; } private static String getNodeName(int nodeIdx) { return "v" + (nodeIdx + 1); }结果打印：v1-->v1最短距离:0 最短路径v1<--v1v1-->v3最短距离:10 最短路径v3<--v1v1-->v4最短距离:50 最短路径v4<--v5<--v1v1-->v5最短距离:30 最短路径v5<--v1v1-->v6最短距离:60 最短路径v6<--v4<--v5<--v1四、扩展
我另外想了一种方法来实现寻找最短路径，类似迪克斯特拉算法，只不过将广度优先搜索变为深度优先搜索
public class DetectShotestDistance { public static final int INF = 65535; public static final String RIGHT_ARROW = "-->"; public static final String LEFT_ARROW = "<--"; public static void main(String[] args) { getShortestDistance(new int[][]{ {0, INF, 10, INF, 30, 100}, {INF, 0, 5, INF, INF, INF}, {INF, INF, 0, 50, INF, INF}, {INF, INF, INF, 0, INF, 10}, {INF, INF, INF, 20, 0, 60}, {INF, INF, INF, INF, INF, 0} }, 0); } private static void getShortestDistance(int[][] matrix, int start) { Set visited = new HashSet<>(); int[] distance = new int[matrix.length]; int[] pre = new int[matrix.length]; // 初始化距离数组和路径数组 for (int j = 0; j < matrix[start].length; j++) { distance[j] = matrix[start][j]; if (distance[j] == INF) { pre[j] = -1; } else { pre[j] = start; } } int curIdx = start; visited.add(curIdx); int nextIdx = getNextNodeIndex(start, matrix, visited, distance, pre); while (nextIdx != -1) { visited.add(nextIdx); if (matrix[curIdx][nextIdx] + distance[curIdx] < distance[nextIdx]) { distance[nextIdx] = matrix[curIdx][nextIdx] + distance[curIdx]; } curIdx = nextIdx; nextIdx = getNextNodeIndex(nextIdx, matrix, visited, distance, pre); } for (int i = 0; i < distance.length; i++) { StringBuilder sb = new StringBuilder(); sb.append(getNodeName(start)); sb.append(RIGHT_ARROW); sb.append(getNodeName(i)); if (distance[i] < INF) { sb.append("最短距离:"); sb.append(distance[i]); sb.append("\t"); } else { sb.append("不通"); continue; } sb.append("最短路径"); sb.append(getNodeName(i)); sb.append(LEFT_ARROW); int j = i; do { j = pre[j]; sb.append(getNodeName(j)); sb.append(LEFT_ARROW); } while (pre[j] != -1 && j != start); System.out.println(sb.substring(0, sb.lastIndexOf(LEFT_ARROW))); } } private static int getNextNodeIndex(int curIdx, int[][] matrix, Set visited, int[] distance, int[] pre) { int min = INF; int minIdx = -1; for (int j = 0; j < matrix[curIdx].length; j++) { if (matrix[curIdx][j] < min && !visited.contains(j)) { min = matrix[curIdx][j]; minIdx = j; pre[minIdx] = curIdx; } } if (minIdx == -1) { for (int j = 0; j < distance.length; j++) { if (distance[j] != INF && !visited.contains(j)) { return j; } } } return minIdx; } private static String getNodeName(int nodeIdx) { return "v" + (nodeIdx + 1); }结果打印：v1-->v1最短距离:0 最短路径v1<--v1v1-->v3最短距离:10 最短路径v3<--v1v1-->v4最短距离:50 最短路径v4<--v5<--v1v1-->v5最短距离:30 最短路径v5<--v1v1-->v6最短距离:60 最短路径v6<--v4<--v5<--v1