# #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 Set<GraphVertex> vertexSet;

/**
* Constructor
*/
DirectedGraphWithWeights() {
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);
WeightedEdge weightedEdge = new WeightedEdge(weight, graphVertexA,
graphVertexB);
}

/**
* Returns all the adjacent nodes
* @param source Source node
* @return Returns all the adjacent nodes
*/
GraphVertex tempNode = new GraphVertex(source);
}

/**
* 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
shortestPathMap.put(edge.getDestination(), edge.getEdgeWeight());
}

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

// Get the adjacent vertices to the currentVertex and update the
// shortestPathMap
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!!!

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