Skip to content

Commit 05f7434

Browse files
liuyuboboboliuyubobobo
committed
Chapter 09 Java completed code added.
1 parent 6ab1cb5 commit 05f7434

File tree

12 files changed

+786
-0
lines changed

12 files changed

+786
-0
lines changed

‎09-Shortest-Path/Course Code (Java)/Chapter-09-Completed-Code/src/bobo/algo/BellmanFord.java

Lines changed: 156 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,156 @@
1+
package bobo.algo;
2+
3+
import java.util.Vector;
4+
import java.util.Stack;
5+
6+
// 使用BellmanFord算法求最短路径
7+
public class BellmanFord<Weight extends Number & Comparable> {
8+
9+
private WeightedGraph G; // 图的引用
10+
private int s; // 起始点
11+
private Number[] distTo; // distTo[i]存储从起始点s到i的最短路径长度
12+
Edge<Weight>[] from; // from[i]记录最短路径中, 到达i点的边是哪一条
13+
// 可以用来恢复整个最短路径
14+
boolean hasNegativeCycle; // 标记图中是否有负权环
15+
16+
// 构造函数, 使用BellmanFord算法求最短路径
17+
public BellmanFord(WeightedGraph graph, int s){
18+
19+
G = graph;
20+
this.s = s;
21+
distTo = new Number[G.V()];
22+
from = new Edge[G.V()];
23+
// 初始化所有的节点s都不可达, 由from数组来表示
24+
for( int i = 0 ; i < G.V() ; i ++ )
25+
from[i] = null;
26+
27+
// 设置distTo[s] = 0, 并且让from[s]不为NULL, 表示初始s节点可达且距离为0
28+
distTo[s] = 0.0;
29+
from[s] = new Edge<Weight>(s, s, (Weight)(Number)(0.0)); // 这里我们from[s]的内容是new出来的, 注意要在析构函数里delete掉
30+
31+
// Bellman-Ford的过程
32+
// 进行V-1次循环, 每一次循环求出从起点到其余所有点, 最多使用pass步可到达的最短距离
33+
for( int pass = 1 ; pass < G.V() ; pass ++ ){
34+
35+
// 每次循环中对所有的边进行一遍松弛操作
36+
// 遍历所有边的方式是先遍历所有的顶点, 然后遍历和所有顶点相邻的所有边
37+
for( int i = 0 ; i < G.V() ; i ++ ){
38+
// 使用我们实现的邻边迭代器遍历和所有顶点相邻的所有边
39+
for( Object item : G.adj(i) ){
40+
Edge<Weight> e = (Edge<Weight>)item;
41+
// 对于每一个边首先判断e->v()可达
42+
// 之后看如果e->w()以前没有到达过， 显然我们可以更新distTo[e->w()]
43+
// 或者e->w()以前虽然到达过, 但是通过这个e我们可以获得一个更短的距离, 即可以进行一次松弛操作, 我们也可以更新distTo[e->w()]
44+
if( from[e.v()] != null && (from[e.w()] == null || distTo[e.v()].doubleValue() + e.wt().doubleValue() < distTo[e.w()].doubleValue()) ){
45+
distTo[e.w()] = distTo[e.v()].doubleValue() + e.wt().doubleValue();
46+
from[e.w()] = e;
47+
}
48+
}
49+
}
50+
}
51+
52+
hasNegativeCycle = detectNegativeCycle();
53+
}
54+
55+
// 判断图中是否有负权环
56+
boolean detectNegativeCycle(){
57+
58+
for( int i = 0 ; i < G.V() ; i ++ ){
59+
for( Object item : G.adj(i) ){
60+
Edge<Weight> e = (Edge<Weight>)item;
61+
if( from[e.v()] != null && distTo[e.v()].doubleValue() + e.wt().doubleValue() < distTo[e.w()].doubleValue() )
62+
return true;
63+
}
64+
}
65+
66+
return false;
67+
}
68+
69+
// 返回图中是否有负权环
70+
boolean negativeCycle(){
71+
return hasNegativeCycle;
72+
}
73+
74+
// 返回从s点到w点的最短路径长度
75+
Number shortestPathTo( int w ){
76+
assert w >= 0 && w < G.V();
77+
assert !hasNegativeCycle;
78+
assert hasPathTo(w);
79+
return distTo[w];
80+
}
81+
82+
// 判断从s点到w点是否联通
83+
boolean hasPathTo( int w ){
84+
assert( w >= 0 && w < G.V() );
85+
return from[w] != null;
86+
}
87+
88+
// 寻找从s到w的最短路径, 将整个路径经过的边存放在vec中
89+
Vector<Edge<Weight>> shortestPath(int w){
90+
91+
assert w >= 0 && w < G.V() ;
92+
assert !hasNegativeCycle ;
93+
assert hasPathTo(w) ;
94+
95+
// 通过from数组逆向查找到从s到w的路径, 存放到栈中
96+
Stack<Edge<Weight>> s = new Stack<Edge<Weight>>();
97+
Edge<Weight> e = from[w];
98+
while( e.v() != this.s ){
99+
s.push(e);
100+
e = from[e.v()];
101+
}
102+
s.push(e);
103+
104+
// 从栈中依次取出元素, 获得顺序的从s到w的路径
105+
Vector<Edge<Weight>> res = new Vector<Edge<Weight>>();
106+
while( !s.empty() ){
107+
e = s.pop();
108+
res.add(e);
109+
}
110+
111+
return res;
112+
}
113+
114+
// 打印出从s点到w点的路径
115+
void showPath(int w){
116+
117+
assert( w >= 0 && w < G.V() );
118+
assert( !hasNegativeCycle );
119+
assert( hasPathTo(w) );
120+
121+
Vector<Edge<Weight>> res = shortestPath(w);
122+
for( int i = 0 ; i < res.size() ; i ++ ){
123+
System.out.print(res.elementAt(i).v() + " -> ");
124+
if( i == res.size()-1 )
125+
System.out.println(res.elementAt(i).w());
126+
}
127+
}
128+
129+
// 测试我们的Bellman-Ford最短路径算法
130+
public static void main(String[] args) {
131+
132+
String filename = "testG2.txt";
133+
//String filename = "testG_negative_circle.txt";
134+
int V = 5;
135+
136+
SparseWeightedGraph<Integer> g = new SparseWeightedGraph<Integer>(V, true);
137+
ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);
138+
139+
System.out.println("Test Bellman-Ford:\n");
140+
BellmanFord<Integer> bellmanFord = new BellmanFord<Integer>(g,0);
141+
if( bellmanFord.negativeCycle() )
142+
System.out.println("The graph contain negative cycle!");
143+
else
144+
for( int i = 1 ; i < V ; i ++ ){
145+
if(bellmanFord.hasPathTo(i)) {
146+
System.out.println("Shortest Path to " + i + " : " + bellmanFord.shortestPathTo(i));
147+
bellmanFord.showPath(i);
148+
}
149+
else
150+
System.out.println("No Path to " + i );
151+
152+
System.out.println("----------");
153+
}
154+
155+
}
156+
}

‎09-Shortest-Path/Course Code (Java)/Chapter-09-Completed-Code/src/bobo/algo/DenseWeightedGraph.java

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
package bobo.algo;
2+
3+
import java.util.Vector;
4+
5+
// 稠密图 - 邻接矩阵
6+
public class DenseWeightedGraph<Weight extends Number & Comparable>
7+
implements WeightedGraph{
8+
9+
private int n; // 节点数
10+
private int m; // 边数
11+
private boolean directed; // 是否为有向图
12+
private Edge<Weight>[][] g; // 图的具体数据
13+
14+
// 构造函数
15+
public DenseWeightedGraph( int n , boolean directed ){
16+
assert n >= 0;
17+
this.n = n;
18+
this.m = 0; // 初始化没有任何边
19+
this.directed = directed;
20+
// g初始化为n*n的布尔矩阵, 每一个g[i][j]均为null, 表示没有任和边
21+
// false为boolean型变量的默认值
22+
g = new Edge[n][n];
23+
for(int i = 0 ; i < n ; i ++)
24+
for(int j = 0 ; j < n ; j ++)
25+
g[i][j] = null;
26+
}
27+
28+
public int V(){ return n;} // 返回节点个数
29+
public int E(){ return m;} // 返回边的个数
30+
31+
// 向图中添加一个边
32+
public void addEdge(Edge e){
33+
34+
assert e.v() >= 0 && e.v() < n ;
35+
assert e.w() >= 0 && e.w() < n ;
36+
37+
if( hasEdge( e.v() , e.w() ) )
38+
return;
39+
40+
g[e.v()][e.w()] = new Edge(e);
41+
if( e.v() != e.w() && !directed )
42+
g[e.w()][e.v()] = new Edge(e.w(), e.v(), e.wt());
43+
44+
m ++;
45+
}
46+
47+
// 验证图中是否有从v到w的边
48+
public boolean hasEdge( int v , int w ){
49+
assert v >= 0 && v < n ;
50+
assert w >= 0 && w < n ;
51+
return g[v][w] != null;
52+
}
53+
54+
// 显示图的信息
55+
public void show(){
56+
57+
for( int i = 0 ; i < n ; i ++ ){
58+
for( int j = 0 ; j < n ; j ++ )
59+
if( g[i][j] != null )
60+
System.out.print(g[i][j].wt()+"\t");
61+
else
62+
System.out.print("NULL\t");
63+
System.out.println();
64+
}
65+
}
66+
67+
// 返回图中一个顶点的所有邻边
68+
// 由于java使用引用机制，返回一个Vector不会带来额外开销,
69+
public Iterable<Edge<Weight>> adj(int v) {
70+
assert v >= 0 && v < n;
71+
Vector<Edge<Weight>> adjV = new Vector<Edge<Weight>>();
72+
for(int i = 0 ; i < n ; i ++ )
73+
if( g[v][i] != null )
74+
adjV.add( g[v][i] );
75+
return adjV;
76+
}
77+
}

‎09-Shortest-Path/Course Code (Java)/Chapter-09-Completed-Code/src/bobo/algo/Dijkstra.java

Lines changed: 145 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,145 @@
1+
package bobo.algo;
2+
3+
import java.util.Vector;
4+
import java.util.Stack;
5+
6+
// Dijkstra算法求最短路径
7+
public class Dijkstra<Weight extends Number & Comparable> {
8+
9+
private WeightedGraph G; // 图的引用
10+
private int s; // 起始点
11+
private Number[] distTo; // distTo[i]存储从起始点s到i的最短路径长度
12+
private boolean[] marked; // 标记数组, 在算法运行过程中标记节点i是否被访问
13+
private Edge<Weight>[] from; // from[i]记录最短路径中, 到达i点的边是哪一条
14+
// 可以用来恢复整个最短路径
15+
16+
// 构造函数, 使用Dijkstra算法求最短路径
17+
public Dijkstra(WeightedGraph graph, int s){
18+
19+
// 算法初始化
20+
G = graph;
21+
assert s >= 0 && s < G.V();
22+
this.s = s;
23+
distTo = new Number[G.V()];
24+
marked = new boolean[G.V()];
25+
from = new Edge[G.V()];
26+
for( int i = 0 ; i < G.V() ; i ++ ){
27+
distTo[i] = 0.0;
28+
marked[i] = false;
29+
from[i] = null;
30+
}
31+
32+
// 使用索引堆记录当前找到的到达每个顶点的最短距离
33+
IndexMinHeap<Weight> ipq = new IndexMinHeap<Weight>(G.V());
34+
35+
// 对于其实点s进行初始化
36+
distTo[s] = 0.0;
37+
from[s] = new Edge<Weight>(s, s, (Weight)(Number)(0.0));
38+
ipq.insert(s, (Weight)distTo[s] );
39+
marked[s] = true;
40+
while( !ipq.isEmpty() ){
41+
int v = ipq.extractMinIndex();
42+
43+
// distTo[v]就是s到v的最短距离
44+
marked[v] = true;
45+
46+
// 对v的所有相邻节点进行更新
47+
for( Object item : G.adj(v) ){
48+
Edge<Weight> e = (Edge<Weight>)item;
49+
int w = e.other(v);
50+
// 如果从s点到w点的最短路径还没有找到
51+
if( !marked[w] ){
52+
// 如果w点以前没有访问过,
53+
// 或者访问过, 但是通过当前的v点到w点距离更短, 则进行更新
54+
if( from[w] == null || distTo[v].doubleValue() + e.wt().doubleValue() < distTo[w].doubleValue() ){
55+
distTo[w] = distTo[v].doubleValue() + e.wt().doubleValue();
56+
from[w] = e;
57+
if( ipq.contain(w) )
58+
ipq.change(w, (Weight)distTo[w] );
59+
else
60+
ipq.insert(w, (Weight)distTo[w] );
61+
}
62+
}
63+
}
64+
}
65+
}
66+
67+
// 返回从s点到w点的最短路径长度
68+
Number shortestPathTo( int w ){
69+
assert w >= 0 && w < G.V();
70+
assert hasPathTo(w);
71+
return distTo[w];
72+
}
73+
74+
// 判断从s点到w点是否联通
75+
boolean hasPathTo( int w ){
76+
assert w >= 0 && w < G.V() ;
77+
return marked[w];
78+
}
79+
80+
// 寻找从s到w的最短路径, 将整个路径经过的边存放在vec中
81+
Vector<Edge<Weight>> shortestPath( int w){
82+
83+
assert w >= 0 && w < G.V();
84+
assert hasPathTo(w);
85+
86+
// 通过from数组逆向查找到从s到w的路径, 存放到栈中
87+
Stack<Edge<Weight>> s = new Stack<Edge<Weight>>();
88+
Edge<Weight> e = from[w];
89+
while( e.v() != this.s ){
90+
s.push(e);
91+
e = from[e.v()];
92+
}
93+
s.push(e);
94+
95+
// 从栈中依次取出元素, 获得顺序的从s到w的路径
96+
Vector<Edge<Weight>> res = new Vector<Edge<Weight>>();
97+
while( !s.empty() ){
98+
e = s.pop();
99+
res.add( e );
100+
}
101+
102+
return res;
103+
}
104+
105+
// 打印出从s点到w点的路径
106+
void showPath(int w){
107+
108+
assert w >= 0 && w < G.V();
109+
assert hasPathTo(w);
110+
111+
Vector<Edge<Weight>> path = shortestPath(w);
112+
for( int i = 0 ; i < path.size() ; i ++ ){
113+
System.out.print( path.elementAt(i).v() + " -> ");
114+
if( i == path.size()-1 )
115+
System.out.println(path.elementAt(i).w());
116+
}
117+
}
118+
119+
120+
// 测试我们的Dijkstra最短路径算法
121+
public static void main(String[] args) {
122+
123+
String filename = "testG1.txt";
124+
int V = 5;
125+
126+
SparseWeightedGraph<Integer> g = new SparseWeightedGraph<Integer>(V, true);
127+
// Dijkstra最短路径算法同样适用于有向图
128+
//SparseGraph<int> g = SparseGraph<int>(V, false);
129+
ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);
130+
131+
System.out.println("Test Dijkstra:\n");
132+
Dijkstra<Integer> dij = new Dijkstra<Integer>(g,0);
133+
for( int i = 1 ; i < V ; i ++ ){
134+
if(dij.hasPathTo(i)) {
135+
System.out.println("Shortest Path to " + i + " : " + dij.shortestPathTo(i));
136+
dij.showPath(i);
137+
}
138+
else
139+
System.out.println("No Path to " + i );
140+
141+
System.out.println("----------");
142+
}
143+
144+
}
145+
}

0 commit comments

Comments
 (0)