2642. Design Graph With Shortest Path Calculator

Difficulty:
Related Topics:
Similar Questions:

Problem

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:

  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:

Solution

/**
 * @param {number} n
 * @param {number[][]} edges
 */
var Graph = function(n, edges) {
    var map = Array(n).fill(0).map(() => []);
    for (var i = 0; i < edges.length; i++) {
        map[edges[i][0]].push([edges[i][1], edges[i][2]]);
    }
    this.map = map;
};

/** 
 * @param {number[]} edge
 * @return {void}
 */
Graph.prototype.addEdge = function(edge) {
    this.map[edge[0]].push([edge[1], edge[2]]);
};

/** 
 * @param {number} node1 
 * @param {number} node2
 * @return {number}
 */
Graph.prototype.shortestPath = function(node1, node2) {
    var visited = {};
    var queue = new MinPriorityQueue();
    queue.enqueue(node1, 0);
    while (queue.size()) {
        var { element, priority } = queue.dequeue();
        if (element === node2) return priority;
        if (visited[element]) continue;
        visited[element] = true;
        this.map[element].forEach(item => {
            queue.enqueue(item[0], item[1] + priority);
        });
    }
    return -1;
};

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

Explain:

nope.

Complexity: