Dijkstra's Algorithm Problems

Network Delay Time

class Solution {
    class State {
        int node;
        int distFromStart;

        public State() {}
        public State(int node, int distFromStart) {
            this.node = node;
            this.distFromStart = distFromStart;
        }
    }

    public int networkDelayTime(int[][] times, int n, int k) {
        List<int[]>[] graph = buildGraph(times, n);
        int[] distTo = dijkstra(graph, k, n);
        int min = -1;

        for (int dist : distTo) {
            min = Math.max(min, dist);
        }

        return min == Integer.MAX_VALUE ? -1 : min;
    }

    private int[] dijkstra(List<int[]>[] graph, int src, int size) {
        int[] distTo = new int[size];
        Arrays.fill(distTo, Integer.MAX_VALUE);

        Queue<State> pq = new PriorityQueue<>((a, b) -> a.distFromStart - b.distFromStart);

        pq.offer(new State(src - 1, 0));
        distTo[src - 1] = 0;

        while (!pq.isEmpty()) {
            State state = pq.poll();
            int curNode = state.node;
            int curDistFromStart = state.distFromStart;
            List<int[]> edges = graph[curNode];

            if (distTo[curNode] < curDistFromStart)
                continue;

            for (int[] edge : edges) {
                int nextNode = edge[0];
                int nextDistFromStart = curDistFromStart + edge[1];

                if (distTo[nextNode] <= nextDistFromStart)
                    continue;

                pq.offer(new State(nextNode, nextDistFromStart));
                distTo[nextNode] = nextDistFromStart;
            }
        }

        return distTo;
    }

    private List<int[]>[] buildGraph(int[][] times, int size) {
        List<int[]>[] graph = new List[size];

        for (int i = 0; i < size; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int[] edge : times) {
            int src = edge[0] - 1, dist = edge[1] - 1, weight = edge[2];

            graph[src].add(new int[] {dist, weight});
        }

        return graph;
    }
}

Cheapest Flights Within K Stops

class Solution {

    record State(
            int node,
            int distFromSource,
            int edgeCountFromSource
    ) {}

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // directed connected positive-weighted simple graph
        List<int[]>[] graph = buildGraph(n, flights);
        int maxEdgeCount = k + 1;
        PriorityQueue<State> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.distFromSource, b.distFromSource));
        int[][] distTo = new int[n][maxEdgeCount + 1];
        for (int i = 0; i < n; i++)
            Arrays.fill(distTo[i], Integer.MAX_VALUE);

        State start = new State(src, 0, 0);
        pq.offer(start);
        distTo[src][0] = 0;
        while (!pq.isEmpty()) {
            State state = pq.poll();

            if (state.distFromSource > distTo[state.node][state.edgeCountFromSource])
                continue;
            if (state.node == dst)
                return state.distFromSource;

            for (int[] edge : graph[state.node]) {
                int to = edge[0], dist = edge[1] + state.distFromSource, edgeCount = state.edgeCountFromSource + 1;

                if (edgeCount > maxEdgeCount || dist >= distTo[to][edgeCount])
                    continue;

                pq.offer(new State(to, dist, edgeCount));
                distTo[to][edgeCount] = dist;
            }
        }

        return -1;
    }

    private List<int[]>[] buildGraph(int n, int[][] edges) {
        List<int[]>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            int from = edge[0], to = edge[1], weight = edge[2];
            graph[from].add(new int[] {to, weight});
        }

        return graph;
    }
}

Minimum Cost to Make at Least One Valid Path in a Grid

• The most important point is to translate the question.

• ArrayDeque can replace PriorityQueue for this question

  • Because weight is either 1 or 0. If it's 1, push the state to the tail of the queue; otherwise, push it to the head
  • Optimize time complexity from $O(ElogE)$ to $O(E)$

class Solution {

    static final int[][] DIR = {{0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    record State(
            int i,
            int j,
            int distFromSource
    ) {}

    public int minCost(int[][] grid) {
        int row = grid.length, col = grid[0].length;
        int distRow = row - 1, distCol = col - 1;
        Deque<State> pq = new ArrayDeque<>();
        // distTo[i][j]: minimal cost to get to node (i, j)
        int[][] distTo = new int[row][col];
        for (int i = 0; i < row; i++)
            Arrays.fill(distTo[i], Integer.MAX_VALUE);

        State start = new State(0, 0, 0);
        pq.add(start);
        distTo[0][0] = 0;
        while (!pq.isEmpty()) {
            State state = pq.removeFirst();

            if (state.distFromSource > distTo[state.i][state.j])
                continue;
            if (state.i == distRow && state.j == distCol)
                return state.distFromSource;

            for (int i = 1; i < DIR.length; i++) {
                int nextRow = state.i + DIR[i][0], nextCol = state.j + DIR[i][1];
                if (isOutOfBound(nextRow, nextCol, row, col))
                    continue;

                int d = grid[state.i][state.j];
                int dist = state.distFromSource + (d == i ? 0 : 1);
                if (dist >= distTo[nextRow][nextCol])
                    continue;
                State next = new State(nextRow, nextCol, dist);
                if (d == i)
                    pq.addFirst(next);
                else
                    pq.addLast(next);
                distTo[nextRow][nextCol] = dist;
            }
        }

        return -1;
    }

    private boolean isOutOfBound(int i, int j, int m, int n) {
        return i < 0 || i >= m || j < 0 || j >= n;
    }

}

Path with Maximum Probability

• Dijkstra variation find longest path

class Solution {

    record State(
            int node,
            double distFromSource
    ) {}

    public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
        // undirected weighted graph (weight: [0, 1])
        List<double[]>[] graph = buildGraph(n, edges, succProb);
        // descending
        PriorityQueue<State> pq = new PriorityQueue<>((a, b) -> Double.compare(b.distFromSource, a.distFromSource));
        double[] distTo = new double[n];
        Arrays.fill(distTo, 0.0);

        State start = new State(start_node, 1.0);
        pq.offer(start);
        distTo[start_node] = 1.0;
        while (!pq.isEmpty()) {
            State state = pq.poll();

            if (Double.compare(state.distFromSource, distTo[state.node]) < 0)
                continue;
            if (state.node == end_node)
                return state.distFromSource;

            for (double[] edge : graph[state.node]) {
                int to = (int) edge[0];
                double dist = state.distFromSource * edge[1];
                if (Double.compare(dist, distTo[to]) <= 0)
                    continue;
                pq.offer(new State(to, dist));
                distTo[to] = dist;
            }
        }

        return 0;
    }

    private List<double[]>[] buildGraph(int n, int[][] edges, double[] weight) {
        List<double[]>[] graph = new List[n];
        for (int i = 0; i < n; i++)
            graph[i] = new ArrayList<>();

        for (int i = 0; i < edges.length; i++) {
            int from = edges[i][0], to = edges[i][1];
            graph[from].add(new double[] {to, weight[i]});
            graph[to].add(new double[] {from, weight[i]});
        }

        return graph;
    }
}

Path With Minimum Effort

class Solution {

    class State {
        int node;
        int distFromStart;

        public State() {}
        public State(int node, int distFromStart) {
            this.node = node;
            this.distFromStart = distFromStart;
        }
    }

    public int minimumEffortPath(int[][] heights) {
        List<int[]>[] graph = buildGraph(heights);
        int row = heights.length, col = heights[0].length;

        return dijkstra(graph, 0, row * col - 1);
    }

    private int dijkstra(List<int[]>[] graph, int src, int dst) {
        int[] distTo = new int[graph.length];
        Arrays.fill(distTo, Integer.MAX_VALUE);

        Queue<State> pq = new PriorityQueue<>((a, b) -> a.distFromStart - b.distFromStart);

        pq.offer(new State(src, 0));
        distTo[src] = 0;

        while (!pq.isEmpty()) {
            State state = pq.poll();
            int curNode = state.node;
            int curDistFromStart = state.distFromStart;
            List<int[]> edges = graph[curNode];

            if (distTo[curNode] < curDistFromStart)
                continue;

            if (curNode == dst) {
                return curDistFromStart;
            }

            for (int[] edge : edges) {
                int nextNode = edge[0];
                int nextDistFromStart = Math.max(curDistFromStart, edge[1]);

                if (distTo[nextNode] <= nextDistFromStart)
                    continue;

                pq.offer(new State(nextNode, nextDistFromStart));
                distTo[nextNode] = nextDistFromStart;
            }
        }

        return -1;
    }

    private List<int[]>[] buildGraph(int[][] heights) {
        int row = heights.length, col = heights[0].length;
        List<int[]>[] graph = new List[row * col];
        int[][] dir = new int[][] {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};

        for (int i = 0; i < graph.length; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++) {
                List<int[]> edges = graph[i * col + j];
                for (int[] d : dir) {
                    int x = i + d[0], y = j + d[1];

                    if (x < 0 || y < 0 || x == row || y == col)
                        continue;

                    edges.add(new int[] {x * col + y, Math.abs(heights[i][j] - heights[x][y])});
                }
            }

        return graph;
    }
}