Dijkstra Algorithm

Dijkstra Algorithm can be used to find shortest path from a single source to all other points in an undirected graph.

//Dijkstra - Single Source Shortest Path on undirected graph
public static long findShortestPath(Map<Integer, Map<Integer, Integer>> propGraph, boolean[] visited, int S, int T) {
    Queue<Node> q = new PriorityQueue<>();
    q.add(new Node(S, 0));

    while(!q.isEmpty()) {
        Node node = q.poll();
        //here could be a case, the same node is added multiple times with diff d. But the priority queue ensures the shortest is picked first.
        //So we just throw away the longer one (as we have visited/taken the shorter one)
        if(visited[node.n]) continue;
        visited[node.n] = true;
        if(node.n==T) {
            return node.d;
        }
        if(propGraph.containsKey(node.n)) {
            for(int child: propGraph.get(node.n).keySet()) {
                //we don't do the compare if v.d > u.d + w(u,v) as in sudo code... here the pq does that job. 
                //we just skip that node when pop out from pq if that node is already included/visited
                q.offer(new Node(child,propGraph.get(node.n).get(child) + node.d ));
            }
        }
    }

    return -1;

}

class Node implements Comparable<Node> {
    int d;
    int n;
    public Node(int n, int d) {
        this.d = d;
        this.n = n;
    }

    public int compareTo(Node that) {
        return this.d - that.d;
    }
}

Another a bit different style version:

https://vjudge.net/contest/220649#problem/C

• do a bit different way for tracking the distance (using an array) and leveraging pq.
• using dx, dy for directions.

public class MillionaireMadness {
    private final int[] dx = {1,-1,0,0};
    private final int[] dy = {0,0,1,-1};

    class Node {
        int x, y;
        int d;

        public Node (int x, int y, int d) {
            this.x = x; this.y = y;
            this.d = d;
        }
    }

    public int solve(int[][] matrix, int m, int n) {
        int[][] dist = new int[m][n];
        for(int i=0; i<m; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        dist[0][0] = 0;
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<Node> q = new PriorityQueue<>((a,b)->a.d - b.d);
        q.offer(new Node(0,0,0));

        while(!q.isEmpty()) {
            Node curr = q.poll();
            visited[curr.x][curr.y] = true;
            if(curr.x==m-1 && curr.y==n-1) return curr.d;
            for(int i=0; i<dx.length; i++) {
                int xx = curr.x + dx[i];
                int yy = curr.y + dy[i];

                if(xx>=0 && xx<m && yy>=0 && yy<n && !visited[xx][yy]) {
                    int diff = matrix[xx][yy] - matrix[curr.x][curr.y];
                    int ladder = diff < 0 ? 0: diff;
                    if(Math.max(dist[curr.x][curr.y], ladder) < dist[xx][yy]) {
                        dist[xx][yy] = Math.max(dist[curr.x][curr.y], ladder);
                        q.offer(new Node(xx, yy, dist[xx][yy]));
                    }
                }

            }

        }

        return dist[m-1][n-1];

    }
}