priority queue insert key value pair java

Question

Background

I am trying to code Dijkstra's algorithm in O(mlogn) time, where m is the number of edges and n is the number of nodes. I am using to find the shortest path between a given starting node and a given ending node. And I'm pretty new at this.

Here is the algorithm I have come up with:

Assume the graph is represented by an adjacency matrix and each node has a row index.

Initialize starting node distance to zero, and all other nodes to inifinity, in the heap.

Create a list of shortest paths, equal to the number of nodes in the graph, set to 0.

While the index of the node that corresponds to the minimum element in the heap 
has no value in the list of shortest paths and heap has node distances, do:
    Remove the minimum node distance from the heap, and bubble as necessary to fill the removed node.
    Put the minimum node distance into the list of shortest paths at its row index.

    For all nodes that were adjacent to the node with the minimum distance (that was just removed), do:
      Update the distances in the heap for the current node, using the following calculation:
        min((deleted node distance + adjacent edge weight), current node's distance)
    Reorganize the heap to be a minimum heap.

Return value in the list of shortest paths at the location of the end node.

This is O(mlogn) because you only update the distances once per edge.

"It takes linear time to initialize the heap, and then we perform m updates at a cost of O(log n) each for a total time of O(mlog n)." - http://www.cs.cmu.edu/~avrim/451f07/lectures/lect1011.pdf

Problem

In order to update the distances from the starting vertex in the correct location in the heap, insertions to the heap must be key-value pairs - with the key being the node (row index) and the value being the distance.

There are lecture slides online that say each entry in a priority queue ADT is a key-value pair (otherwise, how could it prioritize?).

Question

The methods for PriorityQueue have at most one parameter, so how do you insert a key associated with a value?

This must be done in a single file with a specific name (i.e. It is my understanding that I can't make a KeyValuePair class implementing Comparator).

I'd love to hear your thoughts.

Answer 1

To use JDK's implementation of priority queue for your application, you can maintain a Map<Key, Value> in addition to PriorityQueue<Value>. In your case, Key represents a node and Value is an object that holds the shortest distance to a node. To update the distance to a node, you first look up its corresponding distance object in the map. Then, you remove the distance object from the priority queue. Next, you update the distance object. Finally, you insert the distance object back in the priority queue.

Answer 2

Below is the Dijkstra implementation using priority_queue . Here ignore the InputReader class as it is for fast input . We can maintain priority according to "Value" of pair in key value pair . Then choose the Pair with minimum cost i.e value .

import java.io.File;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.List;
import java.util.PriorityQueue;
/** 
 * By: Rajan Parmar
 * At : HackerRank 
 **/
public class Dijkstra { 
     // node ,pair ( neighbor , cost)
    static HashMap < Integer , HashSet <Pair>> node;
    static PrintWriter w;   
    public static void main(String [] s) throws Exception{
        InputReader in;

        boolean online = false;
        String fileName = "input";

        node = new HashMap<Integer, HashSet<Pair>>();


        //ignore online if false it is for online competition
        if (online) {

            //ignore
            in = new InputReader(new FileInputStream(
                    new File(fileName + ".txt")));
            w = new PrintWriter(new FileWriter(fileName + "Output.txt"));
        } else {

            // for fast input output . You can use any input method
            in = new InputReader(System.in);
            w = new PrintWriter(System.out);
        }

        // Actual code starts here
        int t;
        int n, m;
        t = in.nextInt();

        while(t-- > 0){
            n = in.nextInt();
            m = in.nextInt();
            while(m-- > 0){
                int x,y,cost;
                x = in.nextInt();
                y = in.nextInt();
                cost = in.nextInt();

                if(node.get(x)==null){
                    node.put(x, new HashSet());
                    node.get(x).add(new Pair(y,cost));
                }
                else{
                    node.get(x).add(new Pair(y,cost));
                }
                if(node.get(y)==null){
                    node.put(y, new HashSet());
                    node.get(y).add(new Pair(x,cost));
                }
                else{
                    node.get(y).add(new Pair(x,cost));
                }
            }
            int source = in.nextInt();
            Dijkstra(source,n);
            node.clear();
            System.out.println("");
        }
    }

    static void Dijkstra(int start , int n) {

        int dist[] = new int[3001];
        int visited[] = new int[3001];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(visited, 0);
        dist[start] = 0 ;
        PriorityQueue < Pair > pq = new PriorityQueue();

        //this will be prioritized according to VALUES (i.e cost in class Pair)
        pq.add(new Pair(start , 0));
        while(!pq.isEmpty()){
            Pair pr = pq.remove();
            visited[pr.neighbor] = 1;
            for(Pair p:node.get(pr.neighbor)){
                if(dist[p.neighbor] > dist[pr.neighbor] + p.cost){
                    dist[p.neighbor] = dist[pr.neighbor] + p.cost;

                    //add updates cost to vertex through start vertex
                    if(visited[p.neighbor]==0)
                        pq.add(new Pair(p.neighbor ,dist[p.neighbor] ));
                }

            }
        }
        for(int i=1;i<=n;i++){
            if(i==start) continue;
            if(visited[i]==0)
                dist[i]=-1;
            System.out.print(dist[i]+" ");
        }
    }

    static class Pair implements Comparable {

        int neighbor;
        int cost;

        public Pair(int y, int cost) {
            // TODO Auto-generated constructor stub
            neighbor = y;
            this.cost = cost;
        }

        @Override
        public int compareTo(Object o) {
            // TODO Auto-generated method stub
            Pair pr = (Pair)o;

            if(cost > pr.cost)
                return 1;
            else
                return -1;

        }

    }

    //Ignore this class , it is for fast input.
    static class InputReader {

        private InputStream stream;
        private byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int snext() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int[] nextIntArray(int n) {
            int a[] = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public String readString() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}

This will take input in following format .

First line be T (no. of test case).

For each test case next line input will be N and M , where N is no of nodes , M is no of edges.

Next M line contains 3 integers i.e x,y,W. It represents edge between node x and y with weight W.

Next line contain single integer i.e. Source node .

Output :

Print shortest distance to all node from given source node . If node is unreachable print -1.

e.g

Input :

1
6 8
1 2 1
1 5 4
2 5 2
2 3 2
5 6 5
3 6 2
3 4 1
6 4 3
1

Output : (shortest distance of all node from node 1)

1 3 4 3 5