Source code

001package algs44;
002import algs13.Stack;
003import  stdlib.*;
004
005/* ***********************************************************************
006 *  Compilation:  javac FloydWarshall.java
007 *  Execution:    java FloydWarshall V E
008 *  Dependencies: AdjMatrixEdgeWeightedDigraph.java
009 *
010 *  Floyd-Warshall all-pairs shortest path algorithm.
011 *
012 *  % java FloydWarshall 100 500
013 *
014 *  Should check for negative cycles during triple loop; otherwise
015 *  intermediate numbers can get exponentially large.
016 *  Reference: "The Floyd-Warshall algorithm on graphs with negative cycles"
017 *  by Stefan Hougardy
018 *
019 *************************************************************************/
020
021public class FloydWarshall {
022        private double[][] distTo;        // distTo[v][w] = length of    shortest v->w path
023        private DirectedEdge[][] edgeTo;  // edgeTo[v][w] = last edge on shortest v->w path
024
025        public FloydWarshall(AdjMatrixEdgeWeightedDigraph G) {
026                int V = G.V();
027                distTo = new double[V][V];
028                edgeTo = new DirectedEdge[V][V];
029
030                // initialize distances to infinity
031                for (int v = 0; v < V; v++) {
032                        for (int w = 0; w < V; w++) {
033                                distTo[v][w] = Double.POSITIVE_INFINITY;
034                        }
035                }
036
037                // initialize distances using edge-weighted digraph's
038                for (int v = 0; v < G.V(); v++) {
039                        for (DirectedEdge e : G.adj(v)) {
040                                distTo[e.from()][e.to()] = e.weight();
041                                edgeTo[e.from()][e.to()] = e;
042                        }
043                        // in case of self-loops
044                        if (distTo[v][v] >= 0.0) {
045                                distTo[v][v] = 0.0;
046                                edgeTo[v][v] = null;
047                        }
048                }
049
050                // Floyd-Warshall updates
051                for (int i = 0; i < V; i++) {
052                        // compute shortest paths using only 0, 1, ..., i as intermediate vertices
053                        for (int v = 0; v < V; v++) {
054                                if (edgeTo[v][i] == null) continue;    // optimization
055                                for (int w = 0; w < V; w++) {
056                                        if (distTo[v][w] > distTo[v][i] + distTo[i][w]) {
057                                                distTo[v][w] = distTo[v][i] + distTo[i][w];
058                                                edgeTo[v][w] = edgeTo[i][w];
059                                        }
060                                }
061                                if (distTo[v][v] < 0.0) return;  // negative cycle
062                        }
063                }
064        }
065
066        // is there a negative cycle?
067        public boolean hasNegativeCycle() {
068                for (int v = 0; v < distTo.length; v++)
069                        if (distTo[v][v] < 0.0) return true;
070                return false;
071        }
072
073        // negative cycle
074        public Iterable<DirectedEdge> negativeCycle() {
075                for (int v = 0; v < distTo.length; v++) {
076                        // negative cycle in v's predecessor graph
077                        if (distTo[v][v] < 0.0) {
078                                int V = edgeTo.length;
079                                EdgeWeightedDigraph spt = new EdgeWeightedDigraph(V);
080                                for (int w = 0; w < V; w++)
081                                        if (edgeTo[v][w] != null)
082                                                spt.addEdge(edgeTo[v][w]);
083                                EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(spt);
084                                assert finder.hasCycle();
085                                return finder.cycle();
086                        }
087                }
088                return null;
089        }
090
091        // is there a path from v to w?
092        public boolean hasPath(int v, int w) {
093                return distTo[v][w] < Double.POSITIVE_INFINITY;
094        }
095
096
097        // return length of shortest path from v to w
098        public double dist(int v, int w) {
099                return distTo[v][w];
100        }
101
102        // return view of shortest path from v to w, null if no such path
103        public Iterable<DirectedEdge> path(int v, int w) {
104                if (!hasPath(v, w) || hasNegativeCycle()) return null;
105                Stack<DirectedEdge> path = new Stack<>();
106                for (DirectedEdge e = edgeTo[v][w]; e != null; e = edgeTo[v][e.from()]) {
107                        path.push(e);
108                }
109                return path;
110        }
111
112        // check optimality conditions
113        private boolean check(EdgeWeightedDigraph G, int s) {
114
115                // no negative cycle
116                if (!hasNegativeCycle()) {
117                        for (int v = 0; v < G.V(); v++) {
118                                for (DirectedEdge e : G.adj(v)) {
119                                        int w = e.to();
120                                        for (int i = 0; i < G.V(); i++) {
121                                                if (distTo[i][w] > distTo[i][v] + e.weight()) {
122                                                        System.err.println("edge " + e + " is eligible");
123                                                        return false;
124                                                }
125                                        }
126                                }
127                        }
128                }
129                return true;
130        }
131
132
133
134        public static void main(String[] args) {
135
136                // random graph with V vertices and E edges, parallel edges allowed
137                int V = Integer.parseInt(args[0]);
138                int E = Integer.parseInt(args[1]);
139                AdjMatrixEdgeWeightedDigraph G = new AdjMatrixEdgeWeightedDigraph(V);
140                for (int i = 0; i < E; i++) {
141                        int v = (int) (V * Math.random());
142                        int w = (int) (V * Math.random());
143                        double weight = Math.round(100 * (Math.random() - 0.15)) / 100.0;
144                        if (v == w) G.addEdge(new DirectedEdge(v, w, Math.abs(weight)));
145                        else        G.addEdge(new DirectedEdge(v, w, weight));
146                }
147
148                StdOut.println(G);
149
150                // run Floyd-Warshall algorithm
151                FloydWarshall spt = new FloydWarshall(G);
152
153                // print all-pairs shortest path distances
154                StdOut.format("     ");
155                for (int v = 0; v < G.V(); v++) {
156                        StdOut.format("%6d ", v);
157                }
158                StdOut.println();
159                for (int v = 0; v < G.V(); v++) {
160                        StdOut.format("%3d: ", v);
161                        for (int w = 0; w < G.V(); w++) {
162                                if (spt.hasPath(v, w)) StdOut.format("%6.2f ", spt.dist(v, w));
163                                else                   StdOut.format("   Inf ");
164                        }
165                        StdOut.println();
166                }
167
168                // print negative cycle
169                if (spt.hasNegativeCycle()) {
170                        StdOut.println("Negative cost cycle:");
171                        for (DirectedEdge e : spt.negativeCycle())
172                                StdOut.println(e);
173                        StdOut.println();
174                }
175
176                // print all-pairs shortest paths
177                else {
178                        for (int v = 0; v < G.V(); v++) {
179                                for (int w = 0; w < G.V(); w++) {
180                                        if (spt.hasPath(v, w)) {
181                                                StdOut.format("%d to %d (%5.2f)  ", v, w, spt.dist(v, w));
182                                                for (DirectedEdge e : spt.path(v, w))
183                                                        StdOut.print(e + "  ");
184                                                StdOut.println();
185                                        }
186                                        else {
187                                                StdOut.format("%d to %d          no path\n", v, w);
188                                        }
189                                }
190                        }
191                }
192
193        }
194
195}