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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| package com.doumee.core.utils;
|
| import java.util.HashMap;
| import java.util.LinkedList;
| import java.util.Queue;
|
| public class DijkstraUtil {
| private Queue visited;
| int[] distance;
|
| public DijkstraUtil(int len) {
| // TODO Auto-generated constructor stub
| visited = new LinkedList();
| distance = new int[len];
|
| }
|
| private int getIndex(Queue q, int[] dis) {
| int k = -1;
| int min_num = Integer.MAX_VALUE;
| for (int i = 0; i < dis.length; i++) {
| if (!q.contains(i)) {
| if (dis[i] < min_num) {
| min_num = dis[i];
| k = i;
| }
| }
| }
| return k;
| }
|
| public void dijkstra(int[][] weight, Object[] str, int v) {
| HashMap path;
| path = new HashMap();
| for (int i = 0; i < str.length; i++)
| path.put(i, "");
|
| //初始化路径长度数组distance
| for (int i = 0; i < str.length; i++) {
| path.put(i, path.get(i) + "" + str[v]);
| if (i == v)
| distance[i] = 0;
| else if (weight[v][i] != -1) {
| distance[i] = weight[v][i];
| path.put(i, path.get(i) + "-->" + str[i]);
| } else
| distance[i] = Integer.MAX_VALUE;
| }
| visited.add(v);
| while (visited.size() < str.length) {
| int k = getIndex(visited, distance);//获取未访问点中距离源点最近的点
| visited.add(k);
| if (k != -1) {
|
| for (int j = 0; j < str.length; j++) {
| //判断k点能够直接到达的点
| if (weight[k][j] != -1) {
| //通过遍历各点，比较是否有比当前更短的路径，有的话，则更新distance，并更新path。
| if (distance[j] > distance[k] + weight[k][j]) {
| distance[j] = distance[k] + weight[k][j];
| path.put(j, path.get(k) + "-->" + str[j]);
| }
| }
|
| }
| }
| }
| for (int h = 0; h < str.length; h++) {
| System.out.printf(str[v] + "-->" + str[h] + ":" + distance[h] + " ");
| if (distance[h] == Integer.MAX_VALUE)
| System.out.print(str[v] + "-->" + str[h] + "之间没有可通行路径");
| else
| System.out.print(str[v] + "-" + str[h] + "之间有最短路径，具体路径为：" + path.get(h).toString());
| System.out.println();
| }
| visited.clear();
|
| }
|
| public static void main(String[] args) {
| // TODO Auto-generated method stub
| /* int[][] weight = {
| {0, 10, 12, -1, -1, -1},
| {-1, 0, -1, 16, 25, -1},
| {4, 3, 0, 12, -1, 8},
| {-1, -1, -1, 0, 7, -1},
| {-1, -1, -1, -1, 0, -1},
| {-1, -1, -1, 2, -1, 0}};
| String[] str = {"V1", "V2", "V3", "V4", "V5", "V6"};
| int len = str.length;
| DijkstraUtil dijkstra = new DijkstraUtil(len);
| //依次让各点当源点，并调用dijkstra函数
| for (int i = 0; i < str.length; i++) {
| dijkstra.dijkstra(weight, str, i);
| }*/
|
| int[][] weight = {
| {0, 10, 5, 7, -1},
| {-1, 0, 4, 5, 10},
| {-1, 4, 0, 6, 5},
| {-1, 5, 6, 0, 7},
| {-1, -1, -1, -1, 0}};
| String[] str = {"A", "B", "C", "D", "E"};
| DijkstraUtil dijkstra = new DijkstraUtil(str.length);
| dijkstra.dijkstra(weight, str, 0);
| }
|
| }
|
|
