How to Implement Dijkstra Shortest Path Algorithm using Java?

Dijkstra Algorithm

Requirements

Implement the classic Dijkstra’s shortest path algorithm and optimize it for maps. Such algorithms are widely used in geographic information systems (GIS) including MapQuest and GPS-based car navigation systems.

Your goal. Optimize Dijkstra’s algorithm so that it can process thousands of shortest path queries for a given map. Once you read in (and optionally preprocess) the map, your program should solve shortest path problems in sublinear time. One method would be to pre-compute the shortest path for all pairs of vertices; however you cannot afford the quadratic space required to store all of this information. Your goal is to reduce the amount of work involved per shortest path computation, without using excessive space. We suggest a number of potential ideas below which you may choose to implement. Or you can develop and implement your own ideas.

Idea 1. The naive implementation of Dijkstra’s algorithm examines all V vertices in the graph. An obvious strategy to reduce the number of vertices examined is to stop the search as soon as you discover the shortest path to the destination. With this approach, you can make the running time per shortest path query proportional to E’ log V’ where E’ and V’ are the number of edges and vertices examined by Dijkstra’s algorithm. However, this requires some care because just re- initializing all of the distances to ∞ would take time proportional to V. Since you are doing repeated queries, you can speed things up dramatically by only re-initializing those values that changed in the previous query.

Idea 2. You can cut down on the search time further by exploiting the Euclidean geometry of the problem. For general graphs, Dijkstra’s relaxes edge v-w by updating wt[w] to the sum of wt[v] plus the distance from v to w. For maps, we instead update wt[w] to be the sum of wt[v] plus the distance from v to w plus the Euclidean distance from w to d minus the Euclidean distance from v to d. This is known as the A* algorithm. This heuristics affects performance, but not correctness.

Solution:

DijkstraAlgorithm.java

package dijkstraalgorithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import dijkstraalgorithm.Edge;
import dijkstraalgorithm.Graph;
import dijkstraalgorithm.Vertex;

public class DijkstraAlgorithm {

        private final List<Vertex> nodes;
        private final List<Edge> edges;
        private Set<Vertex> settledNodes;
        private Set<Vertex> unSettledNodes;
        private Map<Vertex, Vertex> predecessors;
        private Map<Vertex, Integer> distance;

          public DijkstraAlgorithm(Graph graph) {
                // create a copy of the array so that we can operate on this array
                  this.nodes = new ArrayList<Vertex>(graph.getVertexes());
                   this.edges = new ArrayList<Edge>(graph.getEdges());
           }

        public void execute(Vertex source) {
                settledNodes = new HashSet<Vertex>();
                unSettledNodes = new HashSet<Vertex>();
                distance = new HashMap<Vertex, Integer>();
                predecessors = new HashMap<Vertex, Vertex>();
                distance.put(source, 0);
                unSettledNodes.add(source);
                while (unSettledNodes.size() > 0) {
                        Vertex node = getMinimum(unSettledNodes);
                        settledNodes.add(node);
                        unSettledNodes.remove(node);
                        findMinimalDistances(node);
                }
        }

        private void findMinimalDistances(Vertex node) {
                List<Vertex> adjacentNodes = getNeighbors(node);
                for (Vertex target : adjacentNodes) {
                        if (getShortestDistance(target) > getShortestDistance(node)
                                        + getDistance(node, target)) {
                                distance.put(target, getShortestDistance(node)
                                                + getDistance(node, target));
                                predecessors.put(target, node);
                                unSettledNodes.add(target);
                        }
                }

        }

        private int getDistance(Vertex node, Vertex target) {
                for (Edge edge : edges) {
                        if (edge.getSource().equals(node)
                                        && edge.getDestination().equals(target)) {
                                return edge.getWeight();
                        }
                }
                throw new RuntimeException(“Should not happen”);
        }

        private List<Vertex> getNeighbors(Vertex node) {
                List<Vertex> neighbors = new ArrayList<Vertex>();
                for (Edge edge : edges) {
                        if (edge.getSource().equals(node)
                                       && !isSettled(edge.getDestination())) {
                               neighbors.add(edge.getDestination());
                        }
                }
                return neighbors;
        }

        private Vertex getMinimum(Set<Vertex> vertexes) {
                Vertex minimum = null;
                for (Vertex vertex : vertexes) {
                        if (minimum == null) {
                                minimum = vertex;
                        } else {
                                if (getShortestDistance(vertex) < getShortestDistance(minimum)) {
                                        minimum = vertex;
                                }
                        }
                }
                return minimum;
        }

        private boolean isSettled(Vertex vertex) {
                return settledNodes.contains(vertex);
        }

        private int getShortestDistance(Vertex destination) {
                Integer d = distance.get(destination);
                if (d == null) {
                        return Integer.MAX_VALUE;
                } else {
                        return d;
                }
        }

        /*
         * This method returns the path from the source to the selected target and
         * NULL if no path exists
         */
        public LinkedList<Vertex> getPath(Vertex target) {
                LinkedList<Vertex> path = new LinkedList<Vertex>();
                Vertex step = target;
                // check if a path exists
                if (predecessors.get(step) == null) {
                        return null;
                }
                path.add(step);
                while (predecessors.get(step) != null) {
                        step = predecessors.get(step);
                        path.add(step);
                }
                // Put it into the correct order
                Collections.reverse(path);
                return path;
        }

Edge.java

package dijkstraalgorithm;

import dijkstraalgorithm.Vertex;

public class Edge  {
        private final String id;
        private final Vertex source;
        private final Vertex destination;
        private final int weight;

        public Edge(String id, Vertex source, Vertex destination, int weight) {
                this.id = id;
                this.source = source;
                this.destination = destination;
                this.weight = weight;
        }

        public String getId() {
                return id;
        }
        public Vertex getDestination() {
                return destination;
        }

        public Vertex getSource() {
                return source;
        }
        public int getWeight() {
                return weight;
        }

        @Override
        public String toString() {
                return source + ” ” + destination;
        }

}

Graph.java

package dijkstraalgorithm;

import java.util.List;

public class Graph {
        private final List<Vertex> vertexes;
        private final List<Edge> edges;

        public Graph(List<Vertex> vertexes, List<Edge> edges) {
                this.vertexes = vertexes;
                this.edges = edges;
        }

       public List<Vertex> getVertexes() {
              return vertexes;
        }

        public List<Edge> getEdges() {
                return edges;
        }
}

Main.java

package dijkstraalgorithm;

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.nio.charset.Charset;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 *
 * @author Rashid
 */
public class Main {
   public static void main(String args[]) throws IOException{
        Main d=new Main();
      d.testExcute();
      
    }
   
   public static int countLines(String filename) throws IOException {
    InputStream is = new BufferedInputStream(new FileInputStream(filename));
    try {
        byte[] c = new byte[1024];
        int count = 0;
        int readChars = 0;
        boolean empty = true;
        while ((readChars = is.read(c)) != -1) {
            empty = false;
            for (int i = 0; i < readChars; ++i) {
                if (c[i] == ‘\n’) {
                    ++count;
                }
            }
        }
        return (count == 0 && !empty) ? 1 : count;
    } finally {
        is.close();
    }
}
    private List<Vertex> nodes;
        private List<Edge> edges;

    
        public  void testExcute() throws IOException {
            Path currentRelativePath = Paths.get(“”);
          String s = currentRelativePath.toAbsolutePath().toString()+”/t1.txt”;
          int f =  countLines(s);
        
                nodes = new ArrayList<Vertex>();
                edges = new ArrayList<Edge>();
                for (int i = 0; i <9000 ; i++) {
                        Vertex location = new Vertex(“Node_” + i, “Node_” + i);
                        nodes.add(location);
                }
String line;
  int y= 0;
try (
      
    InputStream fis = new FileInputStream(s);
    InputStreamReader isr = new InputStreamReader(fis, Charset.forName(“UTF-8”));
    BufferedReader br = new BufferedReader(isr);
) {
   
    while ((line = br.readLine()) != null) {
     String[]  arr = line.split(” “);
 
 
     //  System.out.println(arr[3]);
       
        
           
         addLane(“Edge_”+String.valueOf(y)+” “, Integer.parseInt(arr[2]), Integer.parseInt(arr[3]), Integer.parseInt(arr[0]));
    y++;
     
    }
}
              

                // Lets check from location Loc_1 to Loc_1000
                Graph graph = new Graph(nodes, edges);
                DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(graph);
                dijkstra.execute(nodes.get(1000));
                LinkedList<Vertex> path = dijkstra.getPath(nodes.get(2500));

               

              for (Vertex vertex : path) {
              
                 System.out.println(vertex);
                }

        }

        private void addLane(String laneId, int sourceLocNo, int destLocNo,
                        int duration) {
                Edge lane = new Edge(laneId,nodes.get(sourceLocNo), nodes.get(destLocNo), duration );
                edges.add(lane);
        }
}

vertex.java

package dijkstraalgorithm;

public class Vertex {
        final private String id;
        final private String name;

        public Vertex(String id, String name) {
                this.id = id;
                this.name = name;
        }
        public String getId() {
                return id;
        }

        public String getName() {
                return name;
        }

        @Override
        public int hashCode() {
                final int prime = 31;
                int result = 1;
                result = prime * result + ((id == null) ? 0 : id.hashCode());
                return result;
        }

        @Override
        public boolean equals(Object obj) {
                if (this == obj)
                        return true;
                if (obj == null)
                        return false;
                if (getClass() != obj.getClass())
                        return false;
                Vertex other = (Vertex) obj;
                if (id == null) {
                        if (other.id != null)
                                return false;
                } else if (!id.equals(other.id))
                        return false;
                return true;
        }

        @Override
        public String toString() {
                return name;
        }

}

Output Screen:

DijkstraAlgorithm

LEAVE A REPLY

Please enter your comment!
Please enter your name here