单元最短路径

问题分析

• 可参考 图的应用——最短路径

Java 源代码

内含详细注释

package Dijkstra;

public class Dijkstra {

	public static void main(String[] args) {
		float max = Float.MAX_VALUE;
		float[][] a = new float[][] {{0, 0, 0, 0, 0, 0}, {0, max, 10, max, 30, 100}, {0, max, max, 60, max, max}, {0, max, max, max, max, 20}, {0, max, max, 10, max, 50}, {0, max, max, max, max, max}};
		int v = 1;
		int n = 5;
		float[] dist = new float[n + 1];
		int[] prev = new int[n + 1];
		dijkstra(v, a, dist, prev);
		for (int i = 1; i <= n; i++) { if (i != v) { System.out.println(v + "->" + i + " : " + dist[i]); }
		}
	} /**
	 * 单元最短路径问题的 Dijkstra 算法 * @param v: 源顶点
	 * @param a：邻接矩阵
	 * @param dist：存放最短路径
	 * @param prev：存放当前顶点的前一个顶点
	 */
	public static void dijkstra(int v, float[][] a, float[] dist, int[] prev) { int n = dist.length - 1;
		if (v < 1 || v > n) return;
		// 代表当前顶点是否被添加到集合S中
		boolean[] s = new boolean[n + 1];
		// 初始化
		for (int i = 1; i <= n; i++) { dist[i] = a[v][i]; s[i] = false; if (dist[i] == Float.MAX_VALUE) prev[i] = 0; else prev[i] = v;
		}
		dist[v] = 0;
		s[v] = true;
		for (int i = 1; i < n; i++) { float temp = Float.MAX_VALUE; int u = v; for (int j = 1; j <= n; j++) {  // 寻找不在S中的最小值 if (!s[j] && (dist[j] < temp)) {  // 从剩余顶点选择 u = j; temp = dist[j]; } } // 加入s中 s[u] = true; for (int j = 1; j <= n; j++) {  // 更新dist if ((!s[j]) && (a[u][j] < Float.MAX_VALUE)){ float newdist = dist[u] + a[u][j]; if (newdist < dist[j]) { dist[j] = newdist; prev[j] = u; } } }
		}
	}
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
 

1->2 : 10.0
1->3 : 40.0
1->4 : 30.0
1->5 : 60.0

  

 

  
1
  
2
  
3
  
4
 

文章来源: ruochen.blog.csdn.net，作者：若尘，版权归原作者所有，如需转载，请联系作者。

原文链接：ruochen.blog.csdn.net/article/details/106493086