001package algs44; 002/* *********************************************************************** 003 * Compilation: javac DijkstraAllPairsSP.java 004 * Dependencies: EdgeWeightedDigraph.java Dijkstra.java 005 * 006 * Dijkstra's algorithm run from each vertex. 007 * Takes time proportional to E V log V and space proportional to EV. 008 * 009 *************************************************************************/ 010 011public class DijkstraAllPairsSP { 012 private final DijkstraSP[] all; 013 014 public DijkstraAllPairsSP(EdgeWeightedDigraph G) { 015 all = new DijkstraSP[G.V()]; 016 for (int v = 0; v < G.V(); v++) 017 all[v] = new DijkstraSP(G, v); 018 } 019 020 Iterable<DirectedEdge> path(int s, int t) { 021 return all[s].pathTo(t); 022 } 023 024 double dist(int s, int t) { 025 return all[s].distTo(t); 026 } 027}