Dijkstra's Algorithm using Priority Queue on Java

Question

I need to implement Dijkstra's Algorithm using priority queue in Java. Here is my code so far:

public class Node {
        long idNum;
        String label;
        HashSet<Edge> outEdges;
        HashSet<Edge> inEdges;
        int indegree;
        int outdegree; 

        int inNum, outNum;
        HashMap<Node, Edge> incoming, outgoing;

        Node(String label, Long idNum) {
            this.label = label;
            this.idNum = idNum;

            inNum =0;
            outNum=0; 
            incoming = new HashMap<Node, Edge>();
            outgoing = new HashMap<Node, Edge>();

        }
        Node(String Label){
            this.label=label;
        }

        public void addOutgoing(Node n, Edge e){
            if(n==null) return;
            outgoing.put(n,e);
            outNum++;
        }
        public void addIncoming(Node n, Edge e){
            if(n==null) return;
            incoming.put(n, e);
            inNum++;
        }
        public void delIn(Node n){
            incoming.remove(n);
            inNum--; 
        }
        public void delOut(Node n){
            outgoing.remove(n);
            outNum--;
        }

        public int getinNum(){
            return this.inNum; 
        }
        public boolean containsEdge(Edge e){
            if(incoming.containsValue(e) || outgoing.containsValue(e)){
                return true;
            }
            return false;
        }

        String getLabel(){
            return this.label;
        }


    }

    public class Edge {

        long idNum, weight;
        String sLabel, dLabel, eLabel;
        Node sNode, dNode;
        Node from;
        Node to;
        int distance;

        public Edge(long idNum, String sLabel, String dLabel, String eLabel) {
            this.idNum = idNum;
            // this.weight=weight;
            this.sLabel = sLabel;
            this.dLabel = dLabel;
            this.eLabel = eLabel;
        }

        public Edge(Node from, Node to) {
            this.from = from;
            this.to = to;
        }

        long getidNum() {
            return this.idNum;
        }

        public int getDistance() {
            return this.distance;
        }

    }


public class DiGraph implements DiGraph_Interface {
    // private Map<Node, Edge> digraph = new HashMap<Node, Edge>();
    private Map<String, Long> nodes = new HashMap<String, Long>();
    private Set<Node> nodes1 = new HashSet<Node>();
    private Set<Edge> edges = new HashSet<Edge>();
    private Map<Node, Node> edges1 = new HashMap<Node, Node>();
    private Set<Long> edge_ids = new HashSet<Long>();

    public long numEdges = 0;
    public long numNodes = 0;

    public DiGraph() { // default constructor
        // explicitly include this
        // we need to have the default constructor
        // if you then write others, this one will still be there

    }

    @Override
    public boolean addNode(long idNum, String label) {
        Node node = new Node(label, idNum);
        if(nodes.containsKey(label) || idNum <0 || label==null || nodes.containsValue(idNum)){
            return false;
        }
        nodes.put(label, idNum);
        nodes1.add(node);
        numNodes++;
        return true;

    }

    @Override
    public boolean addEdge(long idNum, String sLabel, String dLabel, long weight, String eLabel) {
        Edge e = new Edge(idNum, sLabel, dLabel, eLabel);
        Node n1 = new Node(sLabel, idNum);
        Node n2 = new Node(dLabel, idNum);
        if(edge_ids.contains(idNum)){
            return false;
        }
        for(Node n: nodes1){
            if(n.containsEdge(e)){
                return false;}
        }
        for(Edge edge: edges){
            if(edge.dLabel == dLabel && edge.sLabel == sLabel){return false;}
        }

        boolean check1=false;
        boolean check2=false;
        for(Node n: nodes1){
            if(n.label.equals(sLabel)){
                e.sNode=n; 
                check1=true;
            }
            if(n.label.equals(dLabel)){
                e.dNode=n;
                check2=true;
            }
        }
        if(!check1 || !check2){return false;}

        e.sNode.addOutgoing(e.dNode, e);
        e.dNode.addIncoming(e.sNode,e);

        n1.addOutgoing(n2, e);
        n2.addIncoming(n1, e);
        edge_ids.add(idNum);
        edges.add(e);
        numEdges++;
        return true; 

    }

    @Override
    public boolean delNode(String label) {
        Node node = new Node(label);
        if (!nodes.containsKey(label)) {
            return false;
        }
        if (nodes.containsKey(label) || nodes1.contains(node)) {
            nodes.remove(label, nodes.get(label));
            nodes1.remove(node);
            numNodes--;
            return true;
        }
        Set<Edge> remainingEdges = new HashSet<Edge>();
        for(Edge edge : edges){
            if(!node.containsEdge(edge)){
                remainingEdges.add(edge);
            }
        }   
        edges =  remainingEdges;
        numNodes--;
        return true;
    }

    @Override
    public boolean delEdge(String sLabel, String dLabel) {
        if(!nodes.containsKey(dLabel)|| !nodes.containsKey(sLabel)){
            return false;
        }
        for(Edge edge: edges){
            if(edge.dLabel == dLabel && edge.sLabel == sLabel){
                edge.sNode.delOut(edge.dNode);
                edge.dNode.delIn(edge.sNode);
                long idNum = edge.getidNum();
                numEdges--;
                edges.remove(edge);
                edge_ids.remove(idNum);
                return true;
            }
        }
        return false; 
    }


    @Override
    public long numNodes() {
        return this.numNodes;
    }

    @Override
    public long numEdges() {
        return this.numEdges;
    }

    @Override
    public String[] topoSort() {


        ArrayList<Node> nodeArray = new ArrayList<Node>();
        Stack<Node> nodeStack = new Stack<Node>();
        for(Node n: nodes1){
            nodeArray.add(n);
        }
        String[] topoSort = new String[(int) numNodes]; 
        int counter=0;

        int i=0;
        //for(int i=0; i< numNodes; i++){
            for(Node n: nodes1){

                if(n.inNum==0){
                    nodeStack.push(n);
                }
                if(nodeStack.isEmpty()){
                    return null;
                }
                while(!nodeStack.isEmpty()){
                    nodeStack.pop();
                    nodeArray.remove(n);
                if(n.incoming==null){
                    topoSort[i]=n.getLabel();
                    counter++;
                    i++;
                }
                }
            //}
        }
        if(counter != numNodes){
            return null;
        }
        return topoSort;
    }

    @Override
    public ShortestPathInfo[] shortestPath(String label) {
        Node startNode = new Node(label);

        return null;
    }
}

I need to fill in the shortestPath method and return an array of nodes. However, I am unsure as to how to go about this. I know I need to make a priority queue at some point, but can someone please explain to me how? I have already made the startNode and I know I need to assign to it a distance value of 0 and the rest of the nodes a distance value of infinity. Also where does a comparable come into this?

Answer 1

Starting with your Node class:

public class Node {
    // add a parent attribute to the class
    // this will be used in your shortestPath method
    // i have explained it below
    private Node parent;
}

The Edge class:

public class Edge {
    // why do you have four of these? You only need two
    private Node sNode, dNode;
    private Node from;
    private Node to;
}

Your Directed Graph class looks too complicated to me. You can simplify it a little bit:

public class DiGraph implements DiGraph_Interface {

    private LinkedList<Node>[] adjList;
    private HashSet<Edge> edges;

    // implement the interface methods as you have done
}

The search method in DiGraph:

@Override
public ShortestPathInfo[] shortestPath(String label) {
    PriorityQueue<Node> queue = new PriorityQueue<>(new Comparator() {
        @Override
        public int compare(Object o1, Object o2) {
            Node n1 = (Node) o1;
            Node n2 = (Node) o2;
            // this assumes that lower number is higher priority
            // also, this compare method compares the two string values
            // from the two nodes. If n1.label is lexicographically smaller
            // then n1 will be added high up in the queue
            // you can compare based on the node's idNum too
            // you should implement it based on your requirements
            return n1.label.compareTo(n2.label);
        }
    });

    // create a method getScrNode()
    // in that method, traverse the linkedList to find the srcNode
    // You can do this easily if you keep Map of nodes, like you did in your code
    // but that just takes too much memory
    Node start = getSrcNode(label);
    queue.add(start);
    while (!queue.isEmpty()) {
        /*This is your main exercise. You should solve it yourself.
        Somewhere here you should set the parent of a node
        */            
    }

    // print the path
    if (done) {
        while (current.getParent() != null)
            System.out.println(current.getLabel());
    }
    return null;
}

Answer 2

You can use java.util.TreeSet as a priority queue. It contains methods add() for putting an element into the queue and pollFirst() for taking an element with the lowest value.

For comparison, you can either make the class objects of which you will put into the queue (most probably, it is not simply Node, but rather an additional class that contain a reference to a Node and additional information required to restore the route) implement interface Comparable or create a Comparator and pass it as a parameter to the TreeSet constructor. In either case, you need to implement method compareTo() that will compare nodes by their distances, as it is required by the algorithm.