Dijkstra.java

packagecom.thealgorithms.others;

importjava.util.HashMap;
importjava.util.Map;
importjava.util.NavigableSet;
importjava.util.TreeSet;
/**
 * Dijkstra's algorithm,is a graph search algorithm that solves the
 * single-source shortest path problem for a graph with nonnegative edge path
 * costs, producing a shortest path tree.
 *
 * <p>
 * NOTE: The inputs to Dijkstra's algorithm are a directed and weighted graph
 * consisting of 2 or more nodes, generally represented by an adjacency matrix
 * or list, and a start node.
 *
 * <p>
 * Original source of code:
 * https://rosettacode.org/wiki/Dijkstra%27s_algorithm#Java Also most of the
 * comments are from RosettaCode.
 */
publicfinalclassDijkstra {
privateDijkstra() {
 }

privatestaticfinalGraph.Edge[] GRAPH = {
// Distance from node "a" to node "b" is 7.
// In the current Graph there is no way to move the other way (e,g, from "b" to "a"),
// a new edge would be needed for that
newGraph.Edge("a", "b", 7),
newGraph.Edge("a", "c", 9),
newGraph.Edge("a", "f", 14),
newGraph.Edge("b", "c", 10),
newGraph.Edge("b", "d", 15),
newGraph.Edge("c", "d", 11),
newGraph.Edge("c", "f", 2),
newGraph.Edge("d", "e", 6),
newGraph.Edge("e", "f", 9),
 };
privatestaticfinalStringSTART = "a";
privatestaticfinalStringEND = "e";

/**
 * main function Will run the code with "GRAPH" that was defined above.
 */
publicstaticvoidmain(String[] args) {
Graphg = newGraph(GRAPH);
g.dijkstra(START);
g.printPath(END);
// g.printAllPaths();
 }
}

classGraph {

// mapping of vertex names to Vertex objects, built from a set of Edges

privatefinalMap<String, Vertex> graph;

/**
 * One edge of the graph (only used by Graph constructor)
 */
publicstaticclassEdge {

publicfinalStringv1;
publicfinalStringv2;
publicfinalintdist;

Edge(Stringv1, Stringv2, intdist) {
this.v1 = v1;
this.v2 = v2;
this.dist = dist;
 }
 }

/**
 * One vertex of the graph, complete with mappings to neighbouring vertices
 */
publicstaticclassVerteximplementsComparable<Vertex> {

publicfinalStringname;
// MAX_VALUE assumed to be infinity
publicintdist = Integer.MAX_VALUE;
publicVertexprevious = null;
publicfinalMap<Vertex, Integer> neighbours = newHashMap<>();

Vertex(Stringname) {
this.name = name;
 }

privatevoidprintPath() {
if (this == this.previous) {
System.out.printf("%s", this.name);
 } elseif (this.previous == null) {
System.out.printf("%s(unreached)", this.name);
 } else {
this.previous.printPath();
System.out.printf(" -> %s(%d)", this.name, this.dist);
 }
 }

publicintcompareTo(Vertexother) {
if (dist == other.dist) {
returnname.compareTo(other.name);
 }

returnInteger.compare(dist, other.dist);
 }

@Override
publicbooleanequals(Objectobject) {
if (this == object) {
returntrue;
 }
if (object == null || getClass() != object.getClass()) {
returnfalse;
 }
if (!super.equals(object)) {
returnfalse;
 }

Vertexvertex = (Vertex) object;

if (dist != vertex.dist) {
returnfalse;
 }
if (name != null ? !name.equals(vertex.name) : vertex.name != null) {
returnfalse;
 }
if (previous != null ? !previous.equals(vertex.previous) : vertex.previous != null) {
returnfalse;
 }
returnneighbours != null ? neighbours.equals(vertex.neighbours) : vertex.neighbours == null;
 }

@Override
publicinthashCode() {
intresult = super.hashCode();
result = 31 * result + (name != null ? name.hashCode() : 0);
result = 31 * result + dist;
result = 31 * result + (previous != null ? previous.hashCode() : 0);
result = 31 * result + (neighbours != null ? neighbours.hashCode() : 0);
returnresult;
 }

@Override
publicStringtoString() {
return"(" + name + ", " + dist + ")";
 }
 }

/**
 * Builds a graph from a set of edges
 */
Graph(Edge[] edges) {
graph = newHashMap<>(edges.length);

// one pass to find all vertices
for (Edgee : edges) {
if (!graph.containsKey(e.v1)) {
graph.put(e.v1, newVertex(e.v1));
 }
if (!graph.containsKey(e.v2)) {
graph.put(e.v2, newVertex(e.v2));
 }
 }

// another pass to set neighbouring vertices
for (Edgee : edges) {
graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
// graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also do this for an
// undirected graph
 }
 }

/**
 * Runs dijkstra using a specified source vertex
 */
publicvoiddijkstra(StringstartName) {
if (!graph.containsKey(startName)) {
System.err.printf("Graph doesn't contain start vertex \"%s\"%n", startName);
return;
 }
finalVertexsource = graph.get(startName);
NavigableSet<Vertex> q = newTreeSet<>();

// set-up vertices
for (Vertexv : graph.values()) {
v.previous = v == source ? source : null;
v.dist = v == source ? 0 : Integer.MAX_VALUE;
q.add(v);
 }

dijkstra(q);
 }

/**
 * Implementation of dijkstra's algorithm using a binary heap.
 */
privatevoiddijkstra(finalNavigableSet<Vertex> q) {
Vertexu;
Vertexv;
while (!q.isEmpty()) {
// vertex with shortest distance (first iteration will return source)
u = q.pollFirst();
if (u.dist == Integer.MAX_VALUE) {
break; // we can ignore u (and any other remaining vertices) since they are
// unreachable
 }
// look at distances to each neighbour
for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) {
v = a.getKey(); // the neighbour in this iteration

finalintalternateDist = u.dist + a.getValue();
if (alternateDist < v.dist) { // shorter path to neighbour found
q.remove(v);
v.dist = alternateDist;
v.previous = u;
q.add(v);
 }
 }
 }
 }

/**
 * Prints a path from the source to the specified vertex
 */
publicvoidprintPath(StringendName) {
if (!graph.containsKey(endName)) {
System.err.printf("Graph doesn't contain end vertex \"%s\"%n", endName);
return;
 }

graph.get(endName).printPath();
System.out.println();
 }

/**
 * Prints the path from the source to every vertex (output order is not
 * guaranteed)
 */
publicvoidprintAllPaths() {
for (Vertexv : graph.values()) {
v.printPath();
System.out.println();
 }
 }
}