Skip to content

Commit 2f13768

Browse files
shinezejianshinezejian
committed
Dijkstra算法
1 parent 992a946 commit 2f13768

7 files changed

Lines changed: 307 additions & 5 deletions

File tree

‎src/com/zejian/structures/Graph/DirectedWeightGraph/Dijkstra.java‎

Lines changed: 169 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,169 @@
1+
package com.zejian.structures.Graph.DirectedWeightGraph;
2+
3+
import com.zejian.structures.Graph.WeightGraph.Edge;
4+
import com.zejian.structures.Graph.WeightGraph.WeightGraph;
5+
import com.zejian.structures.Graph.WeightGraph.WeightSparseGraph;
6+
import com.zejian.structures.heap.IndexMinPQ;
7+
8+
import java.util.ArrayList;
9+
import java.util.List;
10+
import java.util.Stack;
11+
12+
/**
13+
* Created by zejian on 2018/2/10.
14+
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
15+
* Dijkstra算法(迪杰斯特拉算法),解决无负权边的单源最短路径问题,利用广度优先搜索算法
16+
* 算法思想:
17+
* Dijkstra算法采用的是一种贪心的策略,声明数组 distTo 和 最小索引堆IndexMinPQ ,
18+
* 其中distTo 记录s到每个顶点的最短距离,初始时distTo数组中源点 s 的路径权重为0(distTo[s] = 0)
19+
* 若对于顶点 s 存在能直接到达的边（s,m），则把distTo[m]设为w（s, m）,同时把所有其他（s不能直接到达的）
20+
* 顶点的路径权重设置为-1。
21+
* 利用最小索引堆IndexMinPQ对边的权重进行排序,每次获取某个顶点关联最小权重的边
22+
* 并将当前顶点标记位已被访问,说明源点到该顶点的最短距离已找到.同时搜索该顶点的邻边,将其
23+
* 对应边的权重加入索引堆中以便下轮循环使用,此时需要对顶点进行一次松弛操作更新distTo数组对应值.
24+
* 下次循环中再次从最小索引堆中获取权重最小的边,依次进行上述操作.
25+
*
26+
*/
27+
public class Dijkstra<Weight extends Number & Comparable<Weight>> {
28+
29+
private WeightGraph G;
30+
private int s; //源点
31+
private Number distTo[];//记录s到每个顶点的最短距离
32+
private Edge<Weight> edgeTo[]; //edgeTo[i]记录最短路径中, 到达i点的边是哪一条 可以用来恢复整个最短路径
33+
private boolean marked[]; //标记已被访问的顶点
34+
35+
public Dijkstra(WeightSparseGraph G , int s){
36+
assert G != null;
37+
assert s >= 0;
38+
this.G = G;
39+
this.s = s;
40+
41+
distTo = new Number[G.V()];
42+
edgeTo = new Edge[G.V()];
43+
marked = new boolean[G.V()];
44+
45+
for (int i = 0; i <G.V() ; i++) {
46+
distTo[i] = -1;
47+
}
48+
49+
//算法start
50+
//利用最小索引堆对权重进行排序,保证每次取出来的都是当前集合的最小权重
51+
IndexMinPQ<Weight> pq = new IndexMinPQ<Weight>(G.V());
52+
53+
distTo[s] = 0.0;
54+
Edge<Weight> es = new Edge<Weight>(s,s,(Weight) (Number) 0.0);
55+
edgeTo[s] = es;
56+
pq.insert(s,es.wt());
57+
while (!pq.isEmpty()){
58+
int v = pq.deleteMin();
59+
marked[v] = true;
60+
61+
//遍历邻边
62+
for (Object o: G.adj(v)) {
63+
Edge<Weight> e = (Edge<Weight>) o;
64+
65+
int w = e.other(v);
66+
//如果邻边的顶点最短路径还没有找到,即未被访问
67+
if(!marked[w]){
68+
// 如果w点以前没有访问过,
69+
// 或者访问过, 但是通过当前的v点到w点距离更短, 则进行更新
70+
if(edgeTo[w] == null || distTo[v].doubleValue() + e.wt().doubleValue() < distTo[w].doubleValue()){
71+
distTo[w] = distTo[v].doubleValue() + e.wt().doubleValue();
72+
edgeTo[w] = e;
73+
//更新
74+
if(pq.contains(w)){
75+
pq.change(w,e.wt());
76+
}else {
77+
pq.insert(w,e.wt());
78+
}
79+
}
80+
81+
}
82+
}
83+
}
84+
}
85+
86+
/**
87+
* 获取s到w顶点的最短路径距离
88+
* @param w
89+
* @return
90+
*/
91+
public Number getShortestPathTo(int w){
92+
assert w >= 0 && w < G.V();
93+
assert hasPathTo(w);
94+
return distTo[w];
95+
}
96+
97+
/**
98+
* 从s到w是否可达
99+
* @param w
100+
* @return
101+
*/
102+
public boolean hasPathTo(int w){
103+
assert w >= 0 && w < G.V();
104+
return marked[w];
105+
}
106+
107+
108+
/**
109+
* 寻找从s到w的最短路径, 将整个路径经过的边存放在vec中
110+
* @return
111+
*/
112+
private List<Edge<Weight>> getShortestPath(int w){
113+
assert w >= 0 && w < G.V();
114+
assert hasPathTo(w);
115+
116+
Stack<Edge<Weight>> path = new Stack<>();
117+
118+
Edge<Weight> e = edgeTo[w];
119+
120+
while (e.v() != this.s){
121+
path.push(e);
122+
e = edgeTo[e.v()];
123+
}
124+
125+
path.push(e);
126+
127+
List<Edge<Weight>> pathList = new ArrayList<>();
128+
129+
while (!path.empty()){
130+
pathList.add(path.pop());
131+
}
132+
133+
return pathList;
134+
}
135+
136+
/**
137+
* 打印从s到w顶点的最短路径轨迹
138+
* @param w
139+
*/
140+
public void showShortestPath(int w){
141+
142+
assert w >= 0 && w < G.V();
143+
assert hasPathTo(w);
144+
145+
List<Edge<Weight>> pathList = getShortestPath(w);
146+
147+
for (int i = 0; i < pathList.size() ; i++) {
148+
System.out.print( pathList.get(i).v() + " -> ");
149+
if( i == pathList.size()-1 )
150+
System.out.println(pathList.get(i).w());
151+
}
152+
}
153+
154+
// 测试
155+
public static void main(String[] args) {
156+
String filename = "testDirectedWeightG1.txt";
157+
WeightSparseGraph<Double> wSparseGraph = new WeightSparseGraph<Double>(5,false);
158+
wSparseGraph.readGraph(filename);
159+
wSparseGraph.show();
160+
161+
Dijkstra<Double> d = new Dijkstra<>(wSparseGraph,0);
162+
163+
for (int i = 0; i <wSparseGraph.V() ; i++) {
164+
System.out.println("从s到"+i+"顶点的最短路径w="+d.getShortestPathTo(i));
165+
d.showShortestPath(i);
166+
}
167+
}
168+
169+
}

‎src/com/zejian/structures/Graph/WeightGraph/KruskalMST.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,7 @@ public KruskalMST(WeightGraph graph){
3333
//因为是无向图,存在重复边.所以这里需要判断一下如(0,1)和(1,0)是同一条边
3434
if (e.v() < e.w()) {
3535
count ++;
36-
System.out.println("count:"+count+",e="+e.toString());
36+
// System.out.println("count:"+count+",e="+e.toString());
3737
pq.insert(e);
3838
}
3939
}
@@ -79,7 +79,7 @@ Number mstWeight(){
7979

8080

8181
/**
82-
* TODO:测试未通过.............
82+
* Test
8383
* @param args
8484
*/
8585
public static void main(String[] args) {

‎src/com/zejian/structures/Graph/WeightGraph/LazyPrimMST.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
/**
99
* Created by zejian on 2018/1/29.
1010
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
11-
* 基于切分定理实现的延时最小生成树算法:
11+
* 基于切分定理实现的延时最小生成树算法(针对无向图):
1212
* 利用深度优先搜索算法遍历图,并标记已被访问过的顶点,同时利用最小堆的特性
1313
* 每一次切分,都将新的边的权值加入堆中,并获取从其中获取最小权值的元素,必
1414
* 为最小生成树的一条边的权值

‎src/com/zejian/structures/Graph/WeightGraph/MainTest.java‎

Lines changed: 126 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,126 @@
1+
package com.zejian.structures.Graph.WeightGraph;
2+
3+
/**
4+
* Created by zejian on 2018/2/1.
5+
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
6+
* 比较 KruskaMST LazyPrimMST PrimMST 效率
7+
*/
8+
public class MainTest {
9+
10+
public static void main(String[] args){
11+
12+
String filename1 = "testWG1.txt";
13+
int V1 = 8;
14+
15+
String filename2 = "testWG2-250.txt";
16+
int V2 = 250;
17+
18+
String filename3 = "testWG3-1000.txt";
19+
int V3 = 1000;
20+
21+
String filename4 = "testWG4-10000.txt";
22+
int V4 = 10000;
23+
24+
// 文件读取
25+
WeightSparseGraph<Double> g1 = new WeightSparseGraph<Double>(V1, false);
26+
g1.readGraph(filename1);
27+
System.out.println( filename1 + " load successfully.");
28+
29+
WeightSparseGraph<Double> g2 = new WeightSparseGraph<Double>(V2, false);
30+
g2.readGraph(filename2);
31+
System.out.println( filename2 + " load successfully.");
32+
33+
WeightSparseGraph<Double> g3 = new WeightSparseGraph<Double>(V3, false);
34+
g3.readGraph(filename3);
35+
System.out.println( filename3 + " load successfully.");
36+
37+
WeightSparseGraph<Double> g4 = new WeightSparseGraph<Double>(V4, false);
38+
g4.readGraph(filename4);
39+
System.out.println( filename4 + " load successfully.");
40+
41+
System.out.println();
42+
43+
44+
long startTime, endTime;
45+
46+
// Test Lazy Prim MST
47+
System.out.println("Test Lazy Prim MST:");
48+
49+
startTime = System.currentTimeMillis();
50+
LazyPrimMST<Double> lazyPrimMST1 = new LazyPrimMST<Double>(g1);
51+
endTime = System.currentTimeMillis();
52+
System.out.println("Test for G1: " + (endTime-startTime) + "ms.");
53+
54+
startTime = System.currentTimeMillis();
55+
LazyPrimMST<Double> lazyPrimMST2 = new LazyPrimMST<Double>(g2);
56+
endTime = System.currentTimeMillis();
57+
System.out.println("Test for G2: " + (endTime-startTime) + "ms.");
58+
59+
startTime = System.currentTimeMillis();
60+
LazyPrimMST<Double> lazyPrimMST3 = new LazyPrimMST<Double>(g3);
61+
endTime = System.currentTimeMillis();
62+
System.out.println("Test for G3: " + (endTime-startTime) + "ms.");
63+
64+
startTime = System.currentTimeMillis();
65+
LazyPrimMST<Double> lazyPrimMST4 = new LazyPrimMST<Double>(g4);
66+
endTime = System.currentTimeMillis();
67+
System.out.println("Test for G4: " + (endTime-startTime) + "ms.");
68+
69+
System.out.println();
70+
71+
72+
// Test Prim MST
73+
System.out.println("Test Prim MST:");
74+
75+
startTime = System.currentTimeMillis();
76+
PrimMST<Double> primMST1 = new PrimMST<Double>(g1);
77+
endTime = System.currentTimeMillis();
78+
System.out.println("Test for G1: " + (endTime-startTime) + "ms.");
79+
80+
startTime = System.currentTimeMillis();
81+
PrimMST<Double> primMST2 = new PrimMST<Double>(g2);
82+
endTime = System.currentTimeMillis();
83+
System.out.println("Test for G2: " + (endTime-startTime) + "ms.");
84+
85+
startTime = System.currentTimeMillis();
86+
PrimMST<Double> primMST3 = new PrimMST<Double>(g3);
87+
endTime = System.currentTimeMillis();
88+
System.out.println("Test for G3: " + (endTime-startTime) + "ms.");
89+
90+
startTime = System.currentTimeMillis();
91+
PrimMST<Double> primMST4 = new PrimMST<Double>(g4);
92+
endTime = System.currentTimeMillis();
93+
System.out.println("Test for G4: " + (endTime-startTime) + "ms.");
94+
95+
System.out.println();
96+
97+
98+
// Test Kruskal MST
99+
System.out.println("Test Kruskal MST:");
100+
101+
startTime = System.currentTimeMillis();
102+
KruskalMST<Double> kruskalMST1 = new KruskalMST<Double>(g1);
103+
endTime = System.currentTimeMillis();
104+
System.out.println("Test for G1: " + (endTime-startTime) + "ms.");
105+
106+
startTime = System.currentTimeMillis();
107+
KruskalMST<Double> kruskalMST2 = new KruskalMST<Double>(g2);
108+
endTime = System.currentTimeMillis();
109+
System.out.println("Test for G2: " + (endTime-startTime) + "ms.");
110+
111+
startTime = System.currentTimeMillis();
112+
KruskalMST<Double> kruskalMST3 = new KruskalMST<Double>(g3);
113+
endTime = System.currentTimeMillis();
114+
System.out.println("Test for G3: " + (endTime-startTime) + "ms.");
115+
116+
startTime = System.currentTimeMillis();
117+
KruskalMST<Double> kruskalMST4 = new KruskalMST<Double>(g4);
118+
endTime = System.currentTimeMillis();
119+
System.out.println("Test for G4: " + (endTime-startTime) + "ms.");
120+
121+
System.out.println();
122+
}
123+
124+
125+
126+
}

‎src/com/zejian/structures/Graph/WeightGraph/PrimMST.java‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,6 @@
44

55
import java.util.ArrayList;
66
import java.util.List;
7-
import java.util.Observable;
87

98
/**
109
* Created by zejian on 2018/1/30.

‎src/com/zejian/structures/Graph/WeightGraph/WeightSparseGraph.java‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -40,7 +40,6 @@ public int E() {
4040
public void addEdge(Edge e) {
4141
assert e.v() >= 0 && e.v() < V ;
4242
assert e.w() >= 0 && e.w() < V ;
43-
4443
g[e.v()].add(new Edge<Weight>(e));
4544
if( e.v() != e.w() && !directed ) {
4645
g[e.w()].add(new Edge<Weight>(e.w(),e.v(), (Weight) e.wt()));

‎testDirectedWeightG1.txt‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
5 8
2+
0 1 5
3+
0 2 2
4+
0 3 6
5+
1 4 1
6+
2 1 1
7+
2 4 5
8+
2 3 3
9+
3 4 2

0 commit comments

Comments
 (0)