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}