问题描述： > 给定一个有向带权图 `G=(V，E)`，其中每条边的权是一个非负实数。另外，给定 `V` 中的一个顶点，称为源点。现在要计算从源点到所有其它各个顶点的最短路径长度，这里的路径长度是指路径上经过的所有边上的权值之和。 ---- **Dijkstra算法思想:** 按各个顶点与源点之间路径长度的递增次序，生成源点到各个顶点的最短路径的方法，即先求出长度最短的一条路径，再参照它求出长度次短的一条路径，依此类推，直到从源点到其它各个顶点的最短路径全部求出为止。 ---- **算法设计**： - 源点u 。集合S中的顶点到源点的最短路径的长度已经确定，集合V-S中所包含的顶点到源点的最短路径的长度待定。 - 特殊路径：从源点出发只经过S中的点到达V-S中的点的路径。 - 贪心策略：选择特殊路径长度最短的路径，将其相连的V-S中的顶点加入到集合S中。 **求解步骤:** - 步骤1：设计合适的数据结构。带权邻接矩阵C，即如果< u, x >E，令 `C[u][x]=<u, x >` 的权值，否则，`C[u][x]=无穷`；采用数组dist来记录从源点到其它顶点的最短路径长度；采用数组p来记录最短路径； - 步骤2：初始化。令集合S={u}，对于集合V-S中的所有顶点x，设置`dist[x]=C[u][x]` ；如果顶点i与源点相邻，设置 `p[i]=u` ，否则 `p[i]=-1`； - 步骤3：在集合V-S中依照贪心策略来寻找使得dist[x]具有最小值的顶点t，t就是集合V-S中距离源点u最近的顶点。 - 步骤4：将顶点t加入集合S中，同时更新集合V-S； - 步骤5：如果集合V-S为空，算法结束；否则，转步骤6； - 步骤6：对集合V-S中的所有与顶点t相邻的顶点x，如果`dist[x]>dist[t]+C[t][x]`，则`dist[x]=dist[t]+C[t][x]`并设置`p[x]=t`。转步骤3。 ---- ```java public class Dijkstra { private static final int N = Integer.MAX_VALUE; private static final int[][] Graph = { {0, 1, 5, N, N, N, N, N, N}, {1, 0, 3, 7, 5, N, N, N, N}, {5, 3, 0, N, 1, 7, N, N, N}, {N, 7, N, 0, 2, N, 3, N, N}, {N, 5, 1, 2, 0, 3, 6, 9, N}, {N, N, 7, N, 3, 0, N, 5, N}, {N, N, N, 3, 6, N, 0, 2, 7}, {N, N, N, N, 9, 5, 2, 0, 4}, {N, N, N, N, N, N, 7, 4, 0}}; public static void main(String[] args) { dijkstra(0, Graph); } /** * Dijkstra最短路径。 即图中"节点vs"到其它各个节点的最短路径。 * * @param vs 起始节点 * @param Graph 图 */ public static void dijkstra(int vs, int[][] Graph) { int NUM = Graph[0].length; // 前驱节点数组 int[] prenode = new int[NUM]; // 最短距离数组 int[] mindist = new int[NUM]; // 该节点是否已经找到最短路径 boolean[] find = new boolean[NUM]; int vnear = 0; for (int i = 0; i < mindist.length; i++) { prenode[i] = i; mindist[i] = Graph[vs][i]; find[i] = false; } find[vs] = true; for (int v = 1; v < Graph.length; v++) { // 每次循环求得距离vs最近的节点vnear和最短距离min int min = N; for (int j = 0; j < Graph.length; j++) { if (!find[j] && mindist[j] < min) { min = mindist[j]; vnear = j; } } find[vnear] = true; // 根据vnear修正vs到其他所有节点的前驱节点及距离 for (int k = 0; k < Graph.length; k++) { if (!find[k] && (min + Graph[vnear][k]) < mindist[k]) { prenode[k] = vnear; mindist[k] = min + Graph[vnear][k]; } } } for (int i = 0; i < NUM; i++) { System.out.println("v" + vs + "...v" + prenode[i] + "->v" + i + ", s=" + mindist[i]); } } } ``` ----