Introduction

To run Dijkstra on a 2D array, treat each cell as a graph node and each allowed move to a neighbor as an edge with a non-negative cost. The algorithm then finds the minimum total path cost from a start cell to a target cell, which is useful for weighted grid navigation, routing, and puzzle solvers.

Model the Grid as a Graph

Suppose you have a grid where entering each cell has a cost:

1 3 1
1 5 1
4 2 1

You can move up, down, left, or right. Then:

• each cell is a vertex
• each legal move is an edge
• the path cost is the sum of visited-cell costs or move costs, depending on how you define the problem

In many grid problems, the distance to a neighbor is:

currentDistance + grid[nextRow][nextCol]

That keeps the implementation simple and intuitive.

Why Dijkstra Instead of BFS

BFS works only when every move has the same cost. Once different cells or edges have different non-negative weights, you need Dijkstra.

So:

• unweighted grid: BFS is enough
• weighted grid: use Dijkstra

If your weights can be negative, Dijkstra is not valid and you need a different algorithm.

Java Implementation

Here is a complete implementation for a weighted 2D grid.

1import java.util.Arrays;
2import java.util.PriorityQueue;
3
4public class GridDijkstra {
5
6    static class State implements Comparable<State> {
7        int row;
8        int col;
9        int dist;
10
11        State(int row, int col, int dist) {
12            this.row = row;
13            this.col = col;
14            this.dist = dist;
15        }
16
17        @Override
18        public int compareTo(State other) {
19            return Integer.compare(this.dist, other.dist);
20        }
21    }
22
23    public static int shortestPath(int[][] grid, int startRow, int startCol, int endRow, int endCol) {
24        int rows = grid.length;
25        int cols = grid[0].length;
26
27        int[][] dist = new int[rows][cols];
28        for (int[] row : dist) {
29            Arrays.fill(row, Integer.MAX_VALUE);
30        }
31
32        PriorityQueue<State> pq = new PriorityQueue<>();
33        dist[startRow][startCol] = grid[startRow][startCol];
34        pq.offer(new State(startRow, startCol, dist[startRow][startCol]));
35
36        int[] dr = {-1, 1, 0, 0};
37        int[] dc = {0, 0, -1, 1};
38
39        while (!pq.isEmpty()) {
40            State current = pq.poll();
41
42            if (current.dist != dist[current.row][current.col]) {
43                continue;
44            }
45
46            if (current.row == endRow && current.col == endCol) {
47                return current.dist;
48            }
49
50            for (int i = 0; i < 4; i++) {
51                int nr = current.row + dr[i];
52                int nc = current.col + dc[i];
53
54                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
55                    continue;
56                }
57
58                int newDist = current.dist + grid[nr][nc];
59                if (newDist < dist[nr][nc]) {
60                    dist[nr][nc] = newDist;
61                    pq.offer(new State(nr, nc, newDist));
62                }
63            }
64        }
65
66        return -1;
67    }
68
69    public static void main(String[] args) {
70        int[][] grid = {
71            {1, 3, 1},
72            {1, 5, 1},
73            {4, 2, 1}
74        };
75
76        System.out.println(shortestPath(grid, 0, 0, 2, 2));
77    }
78}

This version includes the starting cell cost in the total distance. If your problem statement defines cost differently, adjust the initialization accordingly.

Why the Priority Queue Matters

Dijkstra repeatedly expands the node with the smallest known tentative distance. A priority queue makes that efficient.

The if (current.dist != dist[current.row][current.col]) check is also important. It skips stale queue entries that were inserted before a shorter path to the same cell was found.

Without that stale-entry guard, the code still may be correct, but it will do unnecessary work.

Obstacles and Blocked Cells

If some cells are impassable, represent them with a sentinel and skip them:

if (grid[nr][nc] == -1) {
    continue;
}

That keeps the graph model consistent. The blocked cell simply has no traversable incoming move in the algorithm.

Recovering the Actual Path

The example above returns only the minimum cost. If you also want the path, store a parent pointer for each cell:

• 'parentRow[row][col]'
• 'parentCol[row][col]'

Whenever you relax a distance, record the current cell as the parent. After reaching the target, walk backward from the end cell to reconstruct the route.

That is the standard extension when the problem asks for both optimal cost and the actual sequence of moves.

Common Pitfalls

• Using BFS on a weighted grid and expecting correct shortest-path results. BFS only works when every move cost is equal.
• Forgetting that Dijkstra requires non-negative edge or cell costs.
• Omitting the stale-priority-queue-entry check, which can make the algorithm much slower on larger grids.
• Mishandling the definition of path cost, especially whether the start cell cost should be counted.
• Failing to bound-check neighbor coordinates before reading grid[nr][nc].

Summary

• A 2D array can be treated as a graph where each cell is a node.
• Dijkstra is the right choice when movement costs are non-negative and not uniform.
• Use a priority queue plus a distance matrix to track the best known path to each cell.
• Add obstacle handling and parent tracking as needed for real pathfinding tasks.
• Be explicit about how you define cost, because that changes both initialization and the final answer.