最短路径-Dijkstra-编程实验室

算法设计

解决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,1，U={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⁡{4+7,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,5+6}=11dis[5]=min⁡{dis[5],dis[2]+4}=min⁡{∞,5+4}=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,6+5}=5（无需修改）dis[5]=min⁡{dis[5],dis[3]+5}=min⁡{9,6+5}=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,9+1}=10dis[6]=min⁡{dis[6],dis[5]+8}=min⁡{∞,9+8}=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,10+6}=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