forked from burakbayramli/books
-
Notifications
You must be signed in to change notification settings - Fork 0
/
FloydWarshall.java
253 lines (230 loc) · 9.21 KB
/
FloydWarshall.java
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
/*************************************************************************
* Compilation: javac FloydWarshall.java
* Execution: java FloydWarshall V E
* Dependencies: AdjMatrixEdgeWeightedDigraph.java
*
* Floyd-Warshall all-pairs shortest path algorithm.
*
* % java FloydWarshall 100 500
*
* Should check for negative cycles during triple loop; otherwise
* intermediate numbers can get exponentially large.
* Reference: "The Floyd-Warshall algorithm on graphs with negative cycles"
* by Stefan Hougardy
*
*************************************************************************/
/**
* The <tt>FloydWarshall</tt> class represents a data type for solving the
* all-pairs shortest paths problem in edge-weighted digraphs with
* no negative cycles.
* The edge weights can be positive, negative, or zero.
* This class finds either a shortest path between every pair of vertices
* or a negative cycle.
* <p>
* This implementation uses the Floyd-Warshall algorithm.
* The constructor takes time proportional to <em>V</em><sup>3</sup> in the
* worst case, where <em>V</em> is the number of vertices.
* Afterwards, the <tt>dist()</tt>, <tt>hasPath()</tt>, and <tt>hasNegativeCycle()</tt>
* methods take constant time; the <tt>path()</tt> and <tt>negativeCycle()</tt>
* method takes time proportional to the number of edges returned.
* <p>
* For additional documentation, see <a href="/algs4/44sp">Section 4.4</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/ public class FloydWarshall {
private boolean hasNegativeCycle; // is there a negative cycle?
private double[][] distTo; // distTo[v][w] = length of shortest v->w path
private DirectedEdge[][] edgeTo; // edgeTo[v][w] = last edge on shortest v->w path
/**
* Computes a shortest paths tree from each vertex to to every other vertex in
* the edge-weighted digraph <tt>G</tt>. If no such shortest path exists for
* some pair of vertices, it computes a negative cycle.
* @param G the edge-weighted digraph
*/
public FloydWarshall(AdjMatrixEdgeWeightedDigraph G) {
int V = G.V();
distTo = new double[V][V];
edgeTo = new DirectedEdge[V][V];
// initialize distances to infinity
for (int v = 0; v < V; v++) {
for (int w = 0; w < V; w++) {
distTo[v][w] = Double.POSITIVE_INFINITY;
}
}
// initialize distances using edge-weighted digraph's
for (int v = 0; v < G.V(); v++) {
for (DirectedEdge e : G.adj(v)) {
distTo[e.from()][e.to()] = e.weight();
edgeTo[e.from()][e.to()] = e;
}
// in case of self-loops
if (distTo[v][v] >= 0.0) {
distTo[v][v] = 0.0;
edgeTo[v][v] = null;
}
}
// Floyd-Warshall updates
for (int i = 0; i < V; i++) {
// compute shortest paths using only 0, 1, ..., i as intermediate vertices
for (int v = 0; v < V; v++) {
if (edgeTo[v][i] == null) continue; // optimization
for (int w = 0; w < V; w++) {
if (distTo[v][w] > distTo[v][i] + distTo[i][w]) {
distTo[v][w] = distTo[v][i] + distTo[i][w];
edgeTo[v][w] = edgeTo[i][w];
}
}
// check for negative cycle
if (distTo[v][v] < 0.0) {
hasNegativeCycle = true;
return;
}
}
}
}
/**
* Is there a negative cycle?
* @return <tt>true</tt> if there is a negative cycle, and <tt>false</tt> otherwise
*/
public boolean hasNegativeCycle() {
return hasNegativeCycle;
}
/**
* Returns a negative cycle, or <tt>null</tt> if there is no such cycle.
* @return a negative cycle as an iterable of edges,
* or <tt>null</tt> if there is no such cycle
*/
public Iterable<DirectedEdge> negativeCycle() {
for (int v = 0; v < distTo.length; v++) {
// negative cycle in v's predecessor graph
if (distTo[v][v] < 0.0) {
int V = edgeTo.length;
EdgeWeightedDigraph spt = new EdgeWeightedDigraph(V);
for (int w = 0; w < V; w++)
if (edgeTo[v][w] != null)
spt.addEdge(edgeTo[v][w]);
EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(spt);
assert finder.hasCycle();
return finder.cycle();
}
}
return null;
}
/**
* Is there a path from the vertex <tt>s</tt> to vertex <tt>t</tt>?
* @param s the source vertex
* @param t the destination vertex
* @return <tt>true</tt> if there is a path from vertex <tt>s</tt>
* to vertex <tt>t</tt>, and <tt>false</tt> otherwise
*/
public boolean hasPath(int s, int t) {
return distTo[s][t] < Double.POSITIVE_INFINITY;
}
/**
* Returns the length of a shortest path from vertex <tt>s</tt> to vertex <tt>t</tt>.
* @param s the source vertex
* @param t the destination vertex
* @return the length of a shortest path from vertex <tt>s</tt> to vertex <tt>t</tt>;
* <tt>Double.POSITIVE_INFINITY</tt> if no such path
* @throws UnsupportedOperationException if there is a negative cost cycle
*/
public double dist(int s, int t) {
if (hasNegativeCycle())
throw new UnsupportedOperationException("Negative cost cycle exists");
return distTo[s][t];
}
/**
* Returns a shortest path from vertex <tt>s</tt> to vertex <tt>t</tt>.
* @param s the source vertex
* @param t the destination vertex
* @return a shortest path from vertex <tt>s</tt> to vertex <tt>t</tt>
* as an iterable of edges, and <tt>null</tt> if no such path
* @throws UnsupportedOperationException if there is a negative cost cycle
*/
public Iterable<DirectedEdge> path(int s, int t) {
if (hasNegativeCycle())
throw new UnsupportedOperationException("Negative cost cycle exists");
if (!hasPath(s, t)) return null;
Stack<DirectedEdge> path = new Stack<DirectedEdge>();
for (DirectedEdge e = edgeTo[s][t]; e != null; e = edgeTo[s][e.from()]) {
path.push(e);
}
return path;
}
// check optimality conditions
private boolean check(EdgeWeightedDigraph G, int s) {
// no negative cycle
if (!hasNegativeCycle()) {
for (int v = 0; v < G.V(); v++) {
for (DirectedEdge e : G.adj(v)) {
int w = e.to();
for (int i = 0; i < G.V(); i++) {
if (distTo[i][w] > distTo[i][v] + e.weight()) {
System.err.println("edge " + e + " is eligible");
return false;
}
}
}
}
}
return true;
}
/**
* Unit tests the <tt>FloydWarshall</tt> data type.
*/
public static void main(String[] args) {
// random graph with V vertices and E edges, parallel edges allowed
int V = Integer.parseInt(args[0]);
int E = Integer.parseInt(args[1]);
AdjMatrixEdgeWeightedDigraph G = new AdjMatrixEdgeWeightedDigraph(V);
for (int i = 0; i < E; i++) {
int v = (int) (V * Math.random());
int w = (int) (V * Math.random());
double weight = Math.round(100 * (Math.random() - 0.15)) / 100.0;
if (v == w) G.addEdge(new DirectedEdge(v, w, Math.abs(weight)));
else G.addEdge(new DirectedEdge(v, w, weight));
}
StdOut.println(G);
// run Floyd-Warshall algorithm
FloydWarshall spt = new FloydWarshall(G);
// print all-pairs shortest path distances
StdOut.printf(" ");
for (int v = 0; v < G.V(); v++) {
StdOut.printf("%6d ", v);
}
StdOut.println();
for (int v = 0; v < G.V(); v++) {
StdOut.printf("%3d: ", v);
for (int w = 0; w < G.V(); w++) {
if (spt.hasPath(v, w)) StdOut.printf("%6.2f ", spt.dist(v, w));
else StdOut.printf(" Inf ");
}
StdOut.println();
}
// print negative cycle
if (spt.hasNegativeCycle()) {
StdOut.println("Negative cost cycle:");
for (DirectedEdge e : spt.negativeCycle())
StdOut.println(e);
StdOut.println();
}
// print all-pairs shortest paths
else {
for (int v = 0; v < G.V(); v++) {
for (int w = 0; w < G.V(); w++) {
if (spt.hasPath(v, w)) {
StdOut.printf("%d to %d (%5.2f) ", v, w, spt.dist(v, w));
for (DirectedEdge e : spt.path(v, w))
StdOut.print(e + " ");
StdOut.println();
}
else {
StdOut.printf("%d to %d no path\n", v, w);
}
}
}
}
}
}