#StackBounty: #java #graph Dijkstra's Algorithm implementation in Java

Bounty: 50

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;
    }
}


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.