/** Single-source shortest paths API */
class DijkstraSingleSourceShortestPath {
// Source
private final int s;
// distTo[v] is length of shortest known path from s to v.
private final double[] distTo;
// edgeTo[w] is last edge on shortest known path from s to w
private final DirectedEdge[] edgeTo;
private IndexMinPQ pq;
public DijkstraSingleSourceShortestPath(EdgeWeightedDigraph G, int s) {
// shortest paths from s in graph G
this.s = s;
this.distTo = new double[G.V()];
this.edgeTo = new DirectedEdge[G.V()];
pq = new IndexMinPQ(G.V());
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
distTo[s] = 0.0;
pq.insert(s, 0.0);
while (!pq.isEmpty()) { // relax vertices in order of distance from s
int v = pq.delMin();
for (DirectedEdge e : G.adj(v))
relax(e);
}
}
/** length of shortest path from s to v */
double distTo(int v) {
return distTo[v];
}
/** shortest path from s to v */
Iterable pathTo(int v) {
Stack path = new Stack<>();
DirectedEdge edge = edgeTo[v];
while(edge != null) {
path.add(edge);
edge = edgeTo[edge.from()];
}
return path;
}
/** is there a path from s to v? */
boolean hasPathTo(int v) {
}
/**
* Relax edge e = v→w.
* distTo[v] is length of shortest known path from s to v.
* distTo[w] is length of shortest known path from s to w.
* edgeTo[w] is last edge on shortest known path from s to w.
* If e = v→w gives shorter path to w through v,
* update both distTo[w] and edgeTo[w].
*/
private void relax(DirectedEdge e) {
int v = e.from(), w = e.to();
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
else pq.insert (w, distTo[w]);
}
}
static class EdgeWeightedDigraph {
private final int V;
private final List[] adj;
/** create an empty edge-weighted digraph with V vertices */
public EdgeWeightedDigraph(int V) {
this.V = V;
adj = new ArrayList[V]; // // create empty graph with V vertices
for (int v = 0; v < V; v++) {
adj[v] = new ArrayList<>();
}
}
/** add weighted directed edge e */
public void addEdge(DirectedEdge e) {
// add edge e = v→w to only v's adjacency list
int v = e.from()
adj[v].add(e);
}
/** edges pointing from v */
public Iterable adj(int v) {
return adj[v];
}
/** all edges in this graph */
Iterable edges() {
Set allEdges = new HashSet<>();
for(List list : adj) {
allEdges.addAll(list);
}
return allEdges;
}
/** number of vertices */
public int V() {
return V;
}
/** number of edges */
int E() {
int edges = 0;
for(List edge : adj) {
edges += edge.size();
}
return edges;
}
}
static class DirectedEdge implements Comparable {
private final int v;
private final int w;
private final double weight;
/** create a weighted edge v-w */
Edge(int v, int w, double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
/** either endpoint */
int from() {
return v;
}
/** the endpoint that's not v */
int to() {
return w;
}
/** compare this edge to that edge */
public int compareTo(Edge that) {
if(this.weight < that.weight) {
return -1;
} else if(this.weight > that.weight) {
return 1;
}
return 0;
}
/** the weight */
double weight() {
return weight;
}
/** string representation */
public String toString() {
return "Edge: " + v + "-" + w + ", Weight: " + weight;
}
}
private static EdgeWeightedDigraph dummyGraph() {
String[][] input = {
{"0", "7", "0.16"},
{"2", "3", "0.17"},
{"1", "7", "0.19"},
{"0", "2", "0.26"},
{"5", "7", "0.28"},
{"1", "3", "0.29"},
{"1", "5", "0.32"},
{"2", "7", "0.34"},
{"4", "5", "0.35"},
{"1", "2", "0.36"},
{"4", "7", "0.37"},
{"0", "4", "0.38"},
{"6", "2", "0.40"},
{"3", "6", "0.52"},
{"6", "0", "0.58"},
{"6", "4", "0.93"}
};
EdgeWeightedDigraph G = new EdgeWeightedDigraph(8);
for(int i = 0; i < input.length; i++) {
int v = Integer.parseInt(input[i][0]);
int w = Integer.parseInt(input[i][1]);
double weight = Double.parseDouble(input[i][2]);
DirectedEdge edge = new DirectedEdge(v, w, weight);
G.addEdge(edge);
}
return G;
}
public static void main (String[] args) {
DijkstraSingleSourceShortestPath dijkstraSingleSourceShortestPath =
new DijkstraSingleSourceShortestPath(dummyGraph());
System.out.println("dijkstraSingleSourceShortestPath: Weight = "
+ dijkstraSingleSourceShortestPath.weight());
System.out.println("MST edges: ");
dijkstraSingleSourceShortestPath.edges()
.forEach(edge ->
System.out.print(edge.either() + "-" + edge.other(edge.either()) + ", "));
}
}
Comments
Post a Comment