LeetCode-in-Java

2642. Design Graph With Shortest Path Calculator

Hard

There is a directed weighted graph that consists of n nodes numbered from 0 to n - 1. The edges of the graph are initially represented by the given array edges where edges[i] = [fromi, toi, edgeCosti] meaning that there is an edge from fromi to toi with the cost edgeCosti.

Implement the Graph class:

• Graph(int n, int[][] edges) initializes the object with n nodes and the given edges.
• addEdge(int[] edge) adds an edge to the list of edges where edge = [from, to, edgeCost]. It is guaranteed that there is no edge between the two nodes before adding this one.
• int shortestPath(int node1, int node2) returns the minimum cost of a path from node1 to node2. If no path exists, return -1. The cost of a path is the sum of the costs of the edges in the path.

Example 1:

Input [“Graph”, “shortestPath”, “shortestPath”, “addEdge”, “shortestPath”] [[4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]], [3, 2], [0, 3], [[1, 3, 4]], [0, 3]]

Output: [null, 6, -1, null, 6]

Explanation:

Graph g = new Graph(4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]);

g.shortestPath(3, 2); // return 6. The shortest path from 3 to 2 in the first diagram above is 3 -> 0 -> 1 -> 2 with a total cost of 3 + 2 + 1 = 6.

g.shortestPath(0, 3); // return -1. There is no path from 0 to 3.

g.addEdge([1, 3, 4]); // We add an edge from node 1 to node 3, and we get the second diagram above.

g.shortestPath(0, 3); // return 6. The shortest path from 0 to 3 now is 0 -> 1 -> 3 with a total cost of 2 + 4 = 6.

Constraints:

• 1 <= n <= 100
• 0 <= edges.length <= n * (n - 1)
• edges[i].length == edge.length == 3
• 0 <= fromi, toi, from, to, node1, node2 <= n - 1
• 1 <= edgeCosti, edgeCost <= 106
• There are no repeated edges and no self-loops in the graph at any point.
• At most 100 calls will be made for addEdge.
• At most 100 calls will be made for shortestPath.

Solution

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Graph {
    private final Map<Integer, ArrayList<Pair<Integer, Integer>>> adj = new HashMap<>();

    public Graph(int n, int[][] edges) {
        for (int i = 0; i < n; i++) {
            adj.put(i, new ArrayList<>());
        }
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int cost = edge[2];
            ArrayList<Pair<Integer, Integer>> uList = adj.get(u);
            uList.add(new Pair<>(v, cost));
            adj.put(u, uList);
        }
    }

    public void addEdge(int[] edge) {
        int u = edge[0];
        int v = edge[1];
        int cost = edge[2];
        ArrayList<Pair<Integer, Integer>> uList = adj.getOrDefault(u, new ArrayList<>());
        uList.add(new Pair<>(v, cost));
        adj.put(u, uList);
    }

    public int shortestPath(int node1, int node2) {
        PriorityQueue<Pair<Integer, Integer>> minHeap =
                new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        int[] distance = new int[adj.size()];
        Arrays.fill(distance, Integer.MAX_VALUE);
        minHeap.add(new Pair<>(node1, 0));
        distance[node1] = 0;
        while (!minHeap.isEmpty()) {
            Pair<Integer, Integer> nodeCost = minHeap.poll();
            int node = nodeCost.getKey();
            int cost = nodeCost.getValue();
            if (node == node2) {
                return cost;
            }
            if (cost > distance[node]) {
                continue;
            }
            ArrayList<Pair<Integer, Integer>> neighbors = adj.get(node);
            if (neighbors != null) {
                for (Pair<Integer, Integer> neighbor : neighbors) {
                    int next = neighbor.getKey();
                    int nextCost = neighbor.getValue();
                    if (cost + nextCost < distance[next]) {
                        distance[next] = cost + nextCost;
                        minHeap.add(new Pair<>(next, cost + nextCost));
                    }
                }
            }
        }
        return -1;
    }

    static class Pair<K, V> {
        private final K key;
        private final V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}

/*
 * Your Graph object will be instantiated and called as such:
 * Graph obj = new Graph(n, edges);
 * obj.addEdge(edge);
 * int param_2 = obj.shortestPath(node1,node2);
 */

This site is open source. Improve this page.