How to store neighbours of a cell in a gird into a priority queue

Question

Say I have a 4 by 4 grid, so 16 cells. Each cell contains a value between 1,5. eg.

     0 1 2 3
     _ _ _ _
0 - |2|1|3|2|
1 - |1|3|5|1|
2 - |5|2|1|4|
3 - |2|4|2|1|

Now I know that I need to use Dijkstra algorithm. Also to optimise this I need to use a Priority queue.

My aim is to find the shortest sum of each cell to a destination. The source can be random on the grid and the destination as well. (i.e. not always top left to bottom right).

I have worked with graphs that use adjacent matrix. However with this grid is it wise to create an adjacent matrix? i.e. set all fields to infinity that aren't neighbours. What would be the most sufficient way of inserting cells into a priority queue? Would it be {(row,col), distance}?

Just to clarify from my understanding, The priority queue will store the best path? So the cell and the accumulative distance. Because, Dijstra's algorithm uses BFS which will search all neighbours for the shortest distance in this case.

Answer 1

Make a 'Node' a class that has 3 fields (row, column, distance) and implements Comparable. Then use Use PriorityQueue<Node>:

import java.util.PriorityQueue;

class Main {

    public static void main(String[] args) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(2, 3, 12));
        pq.add(new Node(0, 9, 1));
        pq.add(new Node(4, 0, 8));

        System.out.println(pq.poll().getDistance()); //prints 1
    }
}

class Node  implements Comparable<Node>{

    private final int row, col, distance;

    public Node(int row, int col, int value) {
        this.row = row;
        this.col = col;
        distance = value;
    }

    int getDistance() {
        return distance;
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(distance, other.distance);
    }
}

Alternatively set a Comperator to the priority queue so Node does not have to implement Comparable:

import java.util.PriorityQueue;

class Main {

    public static void main(String[] args) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Node::compare);
        pq.add(new Node(2, 3, 12));
        pq.add(new Node(0, 9, 1));
        pq.add(new Node(4, 0, 8));

        System.out.println(pq.poll().getDistance()); //prints 1
    }
}

class Node{

    private final int row, col, distance;

    public Node(int row, int col, int value) {
        this.row = row;
        this.col = col;
        distance = value;
    }

    int getDistance() {
        return distance;
    }

    public static int compare(Node o1, Node o2) {
        return Integer.compare(o1.getDistance(), o2.getDistance());
    }
}

You could also use a lambda expression to set a comperator:

PriorityQueue<Node> pq = new PriorityQueue<>((o1,o2)->Integer.compare(o1.getDistance(), o2.getDistance()));

All three options are valid.