Dijkstra's Algorithm implementation in Java

Question

I am learning graph theory in CS and for practice, I have implemented Djikstra's algorithm in Java. I have created a GraphVertex class that contains information about the vertex and WeightedEdge class which contains information about the edges and their weights. DirectedGraphWithHeights class contains the implementation of the algorithm.

I received feedback earlier on Code Review and I have tried to improve on the naming convention I use in the classes.

I wanted to understand if the methodology I am taking towards solving the algorithm and constructing the graph is up to the mark or not.

DirectedGraphWithWeights

public class DirectedGraphWithWeights {

    private HashMap<GraphVertex, LinkedList<WeightedEdge>>
            adjacentVerticesByVertex;
    private Set<GraphVertex> vertexSet;

    /**
     * Constructor
     */
    DirectedGraphWithWeights() {
        adjacentVerticesByVertex = new HashMap<>();
        vertexSet = new HashSet<>();
    }

    /**
     * Returns the number of vertices in the Graph
     * @return Returns the number of vertices
     */
    public int getNumberOfVertices() {
        return this.vertexSet.size();
    }

    /**
     * Adds a node to the graph. VertexA -> VertexB, adding a vertex creates an
     * edge between VertexA and VertexB with the specified weight
     * @param vertexA Vertex A
     * @param vertexB Vertex B
     * @param weight Weight of the edge
     */
    public void addEdge(int vertexA, int vertexB, int weight) {
        GraphVertex graphVertexA = new GraphVertex(vertexA);
        GraphVertex graphVertexB = new GraphVertex(vertexB);
        vertexSet.add(graphVertexA);
        vertexSet.add(graphVertexB);
        WeightedEdge weightedEdge = new WeightedEdge(weight, graphVertexA,
                graphVertexB);
        if(!adjacentVerticesByVertex.containsKey(graphVertexA))
            adjacentVerticesByVertex.put(graphVertexA, new
                    LinkedList<WeightedEdge>());
        adjacentVerticesByVertex.get(graphVertexA).add(weightedEdge);
    }

    /**
     * Returns all the adjacent nodes
     * @param source Source node
     * @return Returns all the adjacent nodes
     */
    public Iterable<WeightedEdge> getAdjacentVertices(int source) {
        GraphVertex tempNode = new GraphVertex(source);
        return adjacentVerticesByVertex.get(tempNode);
    }

    /**
     * Djikstra's algorithm implementation
     */
    public void calculateShortedPath(int source) {
        Set<GraphVertex> visitedVertices = new HashSet<>();
        GraphVertex sourceVertex = new GraphVertex(source);
        HashMap<GraphVertex, Integer> shortestPathMap = new HashMap<>();

        // Set the value of all vertex -> weight to infinity and to the source
        // to 0
        for(GraphVertex vertex : vertexSet) {
            if(vertex.equals(sourceVertex)) shortestPathMap.put(sourceVertex, 0);
            else shortestPathMap.put(vertex, Integer.MAX_VALUE);
        }

        // TODO: Move this to a function later
        // Get all the nodes which can be visited from the start node
        for(WeightedEdge edge : adjacentVerticesByVertex.get(sourceVertex)) {
            shortestPathMap.put(edge.getDestination(), edge.getEdgeWeight());
        }

        visitedVertices.add(sourceVertex);
        // The function will work until there are no more nodes to visit
        while(true) {
            // Next closest vertex
            GraphVertex currentVertex = getLowestWeightVertex(shortestPathMap,
                    visitedVertices);

            if(visitedVertices.size() == vertexSet.size()) {
                break;
            }

            visitedVertices.add(currentVertex);
            // Get the adjacent vertices to the currentVertex and update the
            // shortestPathMap
            if(adjacentVerticesByVertex.containsKey(currentVertex)) {
                for(WeightedEdge edge : adjacentVerticesByVertex.get(currentVertex)) {
                    if(!visitedVertices.contains(edge.getDestination())) {
                        int edgeWeightCumulative =
                                shortestPathMap.get(currentVertex) +
                                        edge.getEdgeWeight();
                        int edgeDestinationWeight =
                                shortestPathMap.get(edge.getDestination());
                        if(edgeWeightCumulative < edgeDestinationWeight) {
                            shortestPathMap.put(edge.getDestination(),
                                    edgeWeightCumulative);
                        }
                    }
                }
            }
        }
        System.out.println(shortestPathMap);
    }

    /**
     * Gets
     * @param shortestPathMap
     * @param visitedVertices
     * @return
     */
    private GraphVertex getLowestWeightVertex(
            HashMap<GraphVertex, Integer> shortestPathMap,
            Set<GraphVertex> visitedVertices) {
        int lowestWeight = Integer.MAX_VALUE;
        GraphVertex lowestVertex = null;
        for(GraphVertex vertex : vertexSet) {
            if(!visitedVertices.contains(vertex)) {
                if(shortestPathMap.get(vertex) < lowestWeight) {
                    lowestWeight = shortestPathMap.get(vertex);
                    lowestVertex = vertex;
                }
            }
        }
        return lowestVertex;
    }
}

WeightedEdge.java

public class WeightedEdge {
    private GraphVertex source;
    private GraphVertex destination;
    private int edgeWeight;

    WeightedEdge(int edgeWeight, GraphVertex source, GraphVertex destination) {
        this.edgeWeight = edgeWeight;
        this.source = source;
        this.destination = destination;
    }

    public GraphVertex getSource() {
        return source;
    }

    public void setSource(GraphVertex source) {
        this.source = source;
    }

    public GraphVertex getDestination() {
        return destination;
    }

    public void setDestination(GraphVertex destination) {
        this.destination = destination;
    }

    public int getEdgeWeight() {
        return edgeWeight;
    }

    public void setEdgeWeight(int edgeWeight) {
        this.edgeWeight = edgeWeight;
    }
}

GraphVertex.java

public class GraphVertex implements Comparator<GraphVertex> {
    private int value;

    GraphVertex(int value) {
        this.value = value;
    }

    public int getValue() {
        return this.value;
    }

    @Override
    public int hashCode() {
        return new Integer(this.value).hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        GraphVertex other = (GraphVertex) obj;
        if(value != other.getValue()) return false;
        return true;
    }

    /**
     * Compares two nodes. The comparison is based on the value in the node
     * @param one
     * @param two
     * @return
     */
    public int compare(GraphVertex one, GraphVertex two) {
        if(one.value == two.value) return 0;
        return one.value > two.value ? 1 : -1;
    }
}

Answer 1

Hey, I think you have pretty nice code there already. Anyways, I have some suggestions:

---

Formatting

This looks pretty good already so please don't take the points to seriously. Mostly it's my personal preferences.

---

I don't like breaking variable definitions like so:

    private HashMap<GraphVertex, LinkedList<WeightedEdge>>
            adjacentVerticesByVertex;

You could mistake it with a function when scrolling over the code.

---

I don't like breaking code like so:

                        int edgeWeightCumulative =
                                shortestPathMap.get(currentVertex) +
                                        edge.getEdgeWeight();

It's harder to read. Usually you want to split what is logically splittable but not single statements.

---

You have more places with strange breaks but I guess you wanted to do it for the post here. Just keep in mind to put a little bit more thoughts into breaks. I won't repeat for the other places.

---

You don't have an empty line at the beginning of DirectedGraphWithWeights like in the other classes. Please decide for one thing and do it consistently.

---

Please add a space after keywords for control structures.

            if(visitedVertices.size() == vertexSet.size()) {
                break;
            }

It will make things more readable.

---

You should add empty space between overall text and keywords in the documentation.

    /**
     * Returns the number of vertices in the Graph
     * @return Returns the number of vertices
     */

---

Naming

---

It's a directed graph so all methods should respect that in naming.

    public void addEdge(int vertexA, int vertexB, int weight) {

A and B can be replaced by Source or Src and Destination or Dest.

---

The value variable in GraphVertex should be named something like index. When it's called value you could assume that two vertices can have the same value for that. As well, this will make the following method much clearer as you notice that vertices are addressed by their index.

    public void addEdge(int vertexA, int vertexB, int weight) {

---

Syntax

---

Don't use this keyword where you don't need to.

    public int getNumberOfVertices() {
        return this.vertexSet.size();
    }

---

One line if statements should be avoided in general but especially multiple ones at the same place.

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        GraphVertex other = (GraphVertex) obj;
        if(value != other.getValue()) return false;
        return true;
    }

It's harder to read for no real benefit in exchange.

---

Consider making adjacentVerticesByVertex and vertexSet final because the reference is never changed.

---

I don't see why you should use a LinkedList here. The benefit is performance when you are removing items often. This is not the case for your code.

    private HashMap<GraphVertex, LinkedList<WeightedEdge>>
            adjacentVerticesByVertex;

---

The temporary variable is not necessary here. Just create the instance in the getter argument.

    public Iterable<WeightedEdge> getAdjacentVertices(int source) {
        GraphVertex tempNode = new GraphVertex(source);
        return adjacentVerticesByVertex.get(tempNode);
    }

---

Documentation

I must say that you don't have the best documentation. It's easy to get the feeling that the reader will understand the code as you do while writing, but that is not the case. Try to write more extensive documentation that includes explanations to the algorithm itself. Also add more detailed documentation to the functions and methods. Keep in mind that in production code, you want to minimize the time someone needs to understand the code. Time is money.

---

Please avoid documentation that is not adding information to the code. In WeightedEdge you didn't add any comments to the trivial methods as it should be. But in DirectedGraphWithWeights you did:

    /**
     * Constructor
     */
    DirectedGraphWithWeights() {
        adjacentVerticesByVertex = new HashMap<>();
        vertexSet = new HashSet<>();
    }

Have a look at ArrayList on GitHub. It's good reference for documentation.

---

Design

While writing I'm checking constantly your logic. I can't find anything realy mentionable and think you did a good job on applying the algorithm itself on the class structure you created.

---

You could have done something different when creating the class structure. The directed graph, including the vertices and edges, and the algorithm itself are two different concepts. Your program could reflect that with an additional class DijkstraAlgorithm or DijkstraSolver that has a static method with a parameter for DirectedGraphWithWeights to apply the algorithm on.

public class DijkstraAlgorithm {
    public static void solve(DirectedGraphWithWeights graph) {
        // Apply algorithm and print the result.
    }
}

Another thing is that an edge can be regarded as a relationship between two vertices. The relationship has three attributes, i.e.:

• One vertex is the source.
• The other is the destination.
• The weight of the relationship.

In your code you made the relationships a map with vertex as key and its relationships as value. This has to be managed like in the following code.

    public void addEdge(int vertexA, int vertexB, int weight) {
        GraphVertex graphVertexA = new GraphVertex(vertexA);
        GraphVertex graphVertexB = new GraphVertex(vertexB);
        vertexSet.add(graphVertexA);
        vertexSet.add(graphVertexB);
        WeightedEdge weightedEdge = new WeightedEdge(weight, graphVertexA,
                graphVertexB);
        if(!adjacentVerticesByVertex.containsKey(graphVertexA))
            adjacentVerticesByVertex.put(graphVertexA, new
                    LinkedList<WeightedEdge>());
        adjacentVerticesByVertex.get(graphVertexA).add(weightedEdge);
    }

As the relationships are seperated from the concept vertex by the class WeightedEdge, the key value is stored in every relationship entity which is redundant. When I get the value for a key vertex, I get a list of WeightedEdge instances that all have the same key vertex as a field. Every vertex should know its relationship to other vertices.

A solution to that is to let every vertex manage its relations itself. As the graph is directed this will be reflected perfectly by a net of such vertices. To represent the weight we can simply make use of a map. An entry represents a key neighbour vertex and a value weight.

public class GraphVertex {
    public final Map<GraphVertex, Integer> edges;
    public final int index; // The 'value' in your version.

    // All the methods needed for the algorithm.
}

Another think you could think about is not having indexing at all because it's not relevant to the algorithm. The algorithm only needs to know the first vertex. The first vertex is always the one that is not the destination of any relationship, or rather edge. The final vertex is the one that is not the source for any relationship, or rather edge. This will ensure that the graph organization is fully representable by the data itself. A class to represent the graph would become redundant. You can keep a variable to give the vertices good names for printing the result.

public class Vertex {
    public final Map<Vertex, Integer> edges;
    public final String name;

    public Vertex(String name) {
        edges = new HashMap<>();
        this.name = name;
    }

    public Vertex addEdge(Vertex other, int weight) {
        edges.put(other, weight);
        return this;
    }

    public static void main(String[] args) {
        Vertex start = new Vertex("start");
        Vertex otherA = new Vertex("otherA");
        Vertex otherB = new Vertex("otherB");
        Vertex end = new Vertex("end");

        start.addEdge(otherA, 1).addEdge(otherB, 2);
        otherA.addEdge(otherB, 3).addEdge(end, 4);
        otherB.addEdge(end, 5);
    }

    // Other stuff.
}

This would limit you to some degree though because you will have a hard time in changing a graph. You will have an even harder time to go through the graph in a different way than from the implicit starting to the ending vertex. A class to manage that would become necessary. Anyways, these are all implementation details and depend on your requirements.

I've found this tutorial that has a very similar approach to what you did. Maybe you can find some impressions there as well.

---

I won't program the whole thing for you to post it here but you should have a good idea about what you could improve in your code to make it more object oriented and cleaner.

Answer 2

I'm by no means a java programmer, just some things I noticed.

---

GraphVertex.equals

This method is messy to say the least. The number of return in this method mixed with if statements with no brackets makes it hard to read. And, it looks like you only want to check one condition, anything else other than that would result in a false return. Now, you only have to check for a null value. Have a look:

@Override
public boolean equals(Object obj) {
    return (obj == null) || (this == obj);
}

GraphVertex.compare

I see you've already used a ternary operator, nice. You can simplify this even further using another ternary operator. Have a look:

public int compare(GraphVertex one, GraphVertex two) {
    return (one.value == two.value) 
        ? 0 
        : (one.value > two.value) 
            ? 1 
            : -1;
}

I used some tabbing to make it more clear what is being compared.

One line if statements

It's a convention to use brackets even when there's only one line after the if statement. It increases readability and makes your code clearer.

Constructors

Unless you want to label a constructor as something other than public, I would keep it, for example, public GraphVertex(int value) { ... }.

DirectedGraphWithWeights.getAdjacentVertices

For this method you don't have to create the variable tempNode. Instead, you can return an anonymous object. Have a look:

public Iterable<WeightedEdge> getAdjacentVertices(int source) {
    return adjacentVerticesByVertex.get(new GraphVertex(source));
}

Better looping

Instead of having one break condition, you can put that inside the while loop. This is so the while loop is solely dependent on that condition, instead of dependent on the break condition. Something like this:

while (visitedVertices.size() == vertexSet.size()) { ... }

Using this

Using this when referencing instance variables can help you keep track of what variables were made in the constructor, and what were made solely in the methods of the class. It's on your discretion.

Answer 3

Two small, related points

public void calculateShortedPath(int source) 

Seems like it should be calculateShortestPath (not Shorted). At the moment the method returns void and is responsible for both calculating the path and printing it out. Consider changing it to return the shortest path instead, so that the caller can decide what it wants to do with the path (print it / use it for navigation). This is likely to make the code easier to reusing going forward.