算法设计解决2个问题如何存放最短路径长度:用一维数组dist[j]存储!源点v默认 dist[j]表示源点 中顶点j的最短路径长度。如dist[2]12表示源点中顶点2的最短路径长度为12。如何存放最短路径:从源点到其他顶点的最短路径有n-1条一条最短路径用一个一维数组表示如从顶点0中5的最短路径为0、2、3、5.表示为path[5]{0,2.3,5}.所有n-1条最短路径可以用二维数组path[]存储。例转为矩阵形式Path 数组说明Path 表示存放最短路径顶点{−1表示源点 0 到顶点没有路径0从源点 0 的最短路径且最短路径上顶点的前一个顶点是源点 0即 path[0]0初始状态距离数组dist[0,4,6,6,∞,∞,∞]路径数组path[0,0,0,−1,−1,−1]计算步骤1 初始化S{0}U{1,2,3,4,5,6}② 在 U中找到最小顶点 1权重最小加入 S{0,1U{2,3,4,5,6}顶点 1 出发有 2, 4 顶点{dis[2]min⁡{dis[2],dis[1]1}min⁡{6,5}5dis[4]min⁡{dis[4],dis[1]7}min⁡{47,6}11修改后dis[0,4,5,6,11,∞,∞]path[0,0,1,0,1,−1,−1]③ 在 U 中找到最小顶点 2权重最小加入 S{0,1,2}S{0,1,2}U{3,4,5,6}顶点 2 出发有 4, 5 顶点{dis[4]min⁡{dis[4],dis[2]6}min⁡{11,56}11dis[5]min⁡{dis[5],dis[2]4}min⁡{∞,54}9修改后dis[0,4,5,6,11,9,∞]dis[0,4,5,6,11,9,∞]path[0,0,1,0,1,2,−1]path[0,0,1,0,1,2,−1]④ 在 U中找到最小顶点 3权重最小加入 S{0,1,2,3}U{4,5,6}顶点 3 出发有 2, 5 顶点{dis[2]min⁡{dis[2],dis[3]5}min⁡{5,65}5无需修改dis[5]min⁡{dis[5],dis[3]5}min⁡{9,65}9无需修改无修改dis[0,4,5,6,11,9,∞]path[0,0,1,0,1,2,−1]⑤ 在 U 中找到最小顶点 5权重最小加入 S{0,1,2,3,5}U{4,6}顶点 5 出发有 4, 6 顶点{dis[4]min⁡{dis[4],dis[5]1}min⁡{11,91}10dis[6]min⁡{dis[6],dis[5]8}min⁡{∞,98}17修改后dis[0,4,5,6,10,9,17]path[0,0,1,0,5,2,5]⑥ 在 U 中找到最小顶点 4权重最小加入 S{0,1,2,3,5,4}U{6}顶点 4 出发有 6 顶点dis[6]min⁡{dis[6],dis[4]6}min⁡{17,106}16修改后dis[0,4,5,6,10,9,16]dis[0,4,5,6,10,9,16]path[0,0,1,0,5,2,4]path[0,0,1,0,5,2,4]⑦ 在 U 中找到最小顶点 6权重最小加入 S{0,1,2,3,5,4,6}U{}顶点 6 出发没有任何顶点 S 包括路径。最终结果最短距离dis[6]16dis[6]16最短路径0→1→2→5→4→6代码java)public class DijkstraAlgorithm { private static final int MAXV 7; private static final int INF Integer.MAX_VALUE / 2; public static void main(String[] args) { MatGraph g new MatGraph(MAXV); g.edges new int[MAXV][MAXV]; // 初始化图 g.edges[0][1] 4; g.edges[0][2] 6; g.edges[0][3] 6; g.edges[0][4] INF; g.edges[0][5] INF; g.edges[0][6] INF; g.edges[1][0] INF; g.edges[1][1] 0; g.edges[1][2] 1; g.edges[1][3] INF; g.edges[1][4] 7; g.edges[1][5] INF; g.edges[1][6] INF; g.edges[2][0] INF; g.edges[2][1] INF; g.edges[2][2] 0; g.edges[2][3] INF; g.edges[2][4] 6; g.edges[2][5] 4; g.edges[2][6] INF; g.edges[3][0] INF; g.edges[3][1] INF; g.edges[3][2] 2; g.edges[3][3] 0; g.edges[3][4] INF; g.edges[3][5] 5; g.edges[3][6] INF; g.edges[4][0] INF; g.edges[4][1] INF; g.edges[4][2] INF; g.edges[4][3] INF; g.edges[4][4] 0; g.edges[4][5] INF; g.edges[4][6] 6; g.edges[5][0] INF; g.edges[5][1] INF; g.edges[5][2] INF; g.edges[5][3] INF; g.edges[5][4] 1; g.edges[5][5] 0; g.edges[5][6] 8; g.edges[6][0] INF; g.edges[6][1] INF; g.edges[6][2] INF; g.edges[6][3] INF; g.edges[6][4] INF; g.edges[6][5] INF; g.edges[6][6] 0; // 对角线元素设为0 for (int i 0; i MAXV; i) { g.edges[i][i] 0; } // 其他位置设为INF for (int i 0; i MAXV; i) { for (int j 0; j MAXV; j) { if (g.edges[i][j] 0 i ! j) { g.edges[i][j] INF; } } } int v 0; // 源点 int[] dist new int[MAXV]; int[] path new int[MAXV]; boolean[] S new boolean[MAXV]; Dijkstra(g, v, dist, path, S); Dispath(g, dist, path, S, v); } public static void Dijkstra(MatGraph g, int v, int[] dist, int[] path, boolean[] S) { for (int i 0; i g.n; i) { dist[i] g.edges[v][i]; S[i] false; if (g.edges[v][i] INF) { path[i] v; } else { path[i] -1; } } S[v] true; path[v] 0; for (int i 0; i g.n - 1; i) { int u findMinDistanceVertex(dist, S); S[u] true; for (int j 0; j g.n; j) { if (!S[j] g.edges[u][j] INF dist[u] g.edges[u][j] dist[j]) { dist[j] dist[u] g.edges[u][j]; path[j] u; } } } } private static int findMinDistanceVertex(int[] dist, boolean[] S) { int minDistance INF; int minIndex -1; for (int j 0; j dist.length; j) { if (!S[j] dist[j] minDistance) { minDistance dist[j]; minIndex j; } } return minIndex; } public static void Dispath(MatGraph g, int[] dist, int[] path, boolean[] S, int v) { for (int i 0; i g.n; i) { if (S[i] i ! v) { System.out.printf(从顶点%d 到顶点%d 的路径长度为: %d 路径为: , v, i, dist[i]); printPath(path, v, i); } } } private static void printPath(int[] path, int v, int i) { if (path[i] -1) { System.out.println(无路径); return; } int[] apath new int[MAXV]; int d 0; apath[d] i; int k path[i]; while (k ! v) { apath[d] k; k path[k]; } apath[d] v; System.out.print(apath[d - 1]); for (int j d - 2; j 0; j--) { System.out.print( - apath[j]); } System.out.println(); } static class MatGraph { int n; int[][] edges; public MatGraph(int n) { this.n n; } } }结果*从顶点0 到顶点1 的路径长度为: 4 路径为: 0 - 1* 从顶点0 到顶点2 的路径长度为: 5 路径为: 0 - 1 - 2* 从顶点0 到顶点3 的路径长度为: 6 路径为: 0 - 3* 从顶点0 到顶点4 的路径长度为: 10 路径为: 0 - 1 - 2 - 5 - 4* 从顶点0 到顶点5 的路径长度为: 9 路径为: 0 - 1 - 2 - 5* 从顶点0 到顶点6 的路径长度为: 16 路径为: 0 - 1 - 2 - 5 - 4 - 6