Dijkstra算法 · jp-hidalgo/javaStructures@2f13768 · GitHub
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

‎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

0 commit comments

Comments
 (0)