Dijkstra’s algorithm – As a Service

Dijikstra shortest path algo

The program is to find the shortest path between two vertexes or nodes in a graph. Where each vertex is having their Edges connected to them, and the weight of them varies. The final goal is to find the less weighted path between two nodes.

You can find the solution in different blogs or platforms. Here we are going to look the problem from a different angel. In real time scenario, there will not be any main program. But the focus will be to write the logic which can get the vertex details from MongoDB and then based on the service layer logic it returns the shortest path of the source and destination mentioned in the request body of controller.

So, the total structure is:

  1. Eureka Service Discovery to enable discovery client  
  2. Controller Layer to receive the request and respond accordingly
  3. Service Layer to process the request based on the business logic written
  4. Dao layer to connect with the mongo DB and fetch the edges and vertexes present

Technology stack:

  1. Spring boot
  2. netflix-eureka-client
  3. Lombok
  4. starter-data-mongodb
  5. apache.commons
  6. zuul (optional) / depends on lead and architectural requirements
  7. Spring Cloud

Service Logic:

Using Priority Queue, we can get the shortest path between the edges and choose the shortest weighted path.

Logic for shortest path: Check for the target if that’s not visited then check the lowest weight and add the vertex in the priority queue.

public void shortestpath(Vertex vertex) {
        vertex.setDistance(0);
        PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
        priorityQueue.add(vertex);
        vertex.setVisited(Boolean.TRUE);
        while (!CollectionUtils.isEmpty(priorityQueue)) {
            Vertex actualVertex = priorityQueue.poll();
            List<Edge> neighbourList = actualVertex.getNeighbouringnodes();
            neighbourList.parallelStream().forEach(edge -> {
                Vertex target = edge.getEnd();
                if (!target.isVisited()) {
                    int newDistance = edge.getWeight() + actualVertex.getDistance();
                    if (newDistance < target.getDistance()) {
                        target.setDistance(newDistance);
                        target.setParentNode(actualVertex);
                        priorityQueue.add(target);
                    }
                }
            });
            actualVertex.setVisited(Boolean.TRUE);
        }

    }

Vertex (Lombok enabled) and Comparable implemented (for shortest path) and Edge Class:

@Document
@Getter @Setter @NoArgsConstructor
@SuppressWarnings("unused")
public class Vertex implements Comparable<Vertex>{
    @Id
    private int vertexId;
    private int distance =Integer.MAX_VALUE;
    private boolean visited;
    private String name;
    private ArrayList<Edge> neighbouringnodes=new ArrayList<>();
    private Vertex parentNode;

    public Vertex(String name){
            this.name=name;
    }
    void addNeighbour(Edge e){
            neighbouringnodes.add(e);
    }

        @Override
    public int compareTo(Vertex vertex) {
        return Integer.compare(this.distance, vertex.distance);
    }
}

Edge class:

@Document
@Getter @Setter @NoArgsConstructor
public class Edge {
    @Id
    private int id;
    private int weight;
    private Vertex start;
    private Vertex end;
    Edge(int weight,Vertex start, Vertex end ){
            this.start=start;
            this.end=end;
            this.weight=weight;
    }
}

Request format: {“startVertex”: “vertexA”, “destinationVertex” : “vertexB” }

vertexA and vertexB are the vertexes’ unique key or name.

The output format will be:

vertexA->vertexB->vertexC

Please follow the git link for finding out the end to end code: https://github.com/dmahapatra/Problem-Solving

Be the first to comment

Leave a Reply

Your email address will not be published.


*