So, I am trying to implement the Dijkstra Algorithm in order to find the shortest path between two cities. So far my classes are :
Edge.java
package com.company;
public class Edge {
private int weight;
private Vertex startVertex;
private Vertex targetVertex;
public Edge(int weight, Vertex startVertex, Vertex targetVertex) {
this.weight = weight;
this.startVertex = startVertex;
this.targetVertex = targetVertex;
}
public double getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public Vertex getStartVertex() {
return startVertex;
}
public void setStartVertex(Vertex startVertex) {
this.startVertex = startVertex;
}
public Vertex getTargetVertex() {
return targetVertex;
}
public void setTargetVertex(Vertex targetVertex) {
this.targetVertex = targetVertex;
}
}
then the Vertex.java
package com.company;
import java.util.ArrayList;
import java.util.List;
public class Vertex implements Comparable<Vertex> {
private String name;
private List<Edge> adjacenciesList;
private boolean visited;
private Vertex predecessor;
private double distance = Double.MAX_VALUE;
public Vertex(String name) {
this.name = name;
this.adjacenciesList = new ArrayList<>();
}
public void addNeighbour(Edge edge) {
this.adjacenciesList.add(edge);
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public List<Edge> getAdjacenciesList() {
return adjacenciesList;
}
public void setAdjacenciesList(List<Edge> adjacenciesList) {
this.adjacenciesList = adjacenciesList;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
public Vertex getPredecessor() {
return predecessor;
}
public void setPredecessor(Vertex predecessor) {
this.predecessor = predecessor;
}
public double getDistance() {
return distance;
}
public void setDistance(double distance) {
this.distance = distance;
}
@Override
public String toString() {
return this.name;
}
@Override
public int compareTo(Vertex otherVertex) {
return Double.compare(this.distance, otherVertex.getDistance());
}
}
and DijkstraShortestPath.java
package com.company;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
public class DjikstraShortestPath {
public void computeShortestPaths(Vertex sourceVertex){
sourceVertex.setDistance(0);
PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
priorityQueue.add(sourceVertex);
sourceVertex.setVisited(true);
while( !priorityQueue.isEmpty() ){
// Getting the minimum distance vertex from priority queue
Vertex actualVertex = priorityQueue.poll();
for(Edge edge : actualVertex.getAdjacenciesList()){
Vertex v = edge.getTargetVertex();
if(!v.isVisited())
{
double newDistance = actualVertex.getDistance() + edge.getWeight();
if( newDistance < v.getDistance() ){
priorityQueue.remove(v);
v.setDistance(newDistance);
v.setPredecessor(actualVertex);
priorityQueue.add(v);
}
}
}
actualVertex.setVisited(true);
}
}
public List<Vertex> getShortestPathTo(Vertex targetVertex){
List<Vertex> path = new ArrayList<>();
for(Vertex vertex=targetVertex;vertex!=null;vertex=vertex.getPredecessor()){
path.add(vertex);
}
Collections.reverse(path);
return path;
}
}
Now, in Main I am trying something like this:
public static void main(String[] args) throws IOException {
{
int i, j;
DjikstraShortestPath shortestPath = new DjikstraShortestPath();
shortestPath.computeShortestPaths(vertex[0]); // setting the source to vertex[0]
for(i=0; i<cities.size(); i++)
{
System.out.println("from"+vertex[0]+"to"+vertex[i]+"the distance is" + vertex[i].getDistance());
System.out.println("Path: "+ shortestPath.getShortestPathTo(vertex[i]));
}
shortestPath.computeShortestPaths(vertex[1]); //changing the source
for(i=0; i<cities.size(); i++)
{
System.out.println("from"+vertex[1]+"to"+vertex[i]+"the distance is" + vertex[i].getDistance());
System.out.println("Path: "+ shortestPath.getShortestPathTo(vertex[i]));
}
}
The problem that I am facing is that the intial source (inital city) vertex[0] when set produces the right result:
for example:
from A to A the distance is 0.0 //A is the main source in this case vertex[0]
path: A
from A to F the distance is 13.5
path: A D C B F
Now when I switch the source to vertex[1]
from B to A the distance is 0.0 //wrong because it uses the data from the previous (vertex[0])
path: A //this is wrong too
from B to F the distance is 13.5
path: A D C B F //uses the previous info from vertex[0] even though the source is changed to vertex[1]
Tried changing the function getShortestPathTo function in DijkstraShortestPath.java to this
public void getShortestPathTo(Vertex targetVertex){
List<Vertex> path = new ArrayList<>();
for(Vertex vertex=targetVertex;vertex!=null;vertex=vertex.getPredecessor()){
path.add(vertex);
}
Collections.reverse(path);
for(int i = 0; i<path.size(); i++)
{
System.out.println(path.get(i).getName());
}
path.clear();
}
}
Made all of the vertices unvisited and now I am facing an "Out of Memory" problem. There is a heap memory problem, I've literally tried everything.
Any help would be appreciated.
Keep safe, and stay at home people!
