Source code

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