# LC 2642. Design Graph With Shortest Path Calculator

### [Problem link](https://leetcode.com/problems/design-graph-with-shortest-path-calculator/)

###### tags: `leedcode` `python` `hard` `Dijkstra`

There is a **directed weighted** graph that consists of <code>n</code> nodes numbered from <code>0</code> to <code>n - 1</code>. The edges of the graph are initially represented by the given array <code>edges</code> where <code>edges[i] = [from_i, to_i, edgeCost_i]</code> meaning that there is an edge from <code>from_i</code> to <code>to_i</code> with the cost <code>edgeCost_i</code>.

Implement the <code>Graph</code> class:

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

**Example 1:**
<img alt="" src="https://assets.leetcode.com/uploads/2023/01/11/graph3drawio-2.png" style="width: 621px; height: 191px;" />

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:**

- <code>1 <= n <= 100</code>
- <code>0 <= edges.length <= n * (n - 1)</code>
- <code>edges[i].length == edge.length == 3</code>
- <code>0 <= from_i, to_i, from, to, node1, node2 <= n - 1</code>
- <code>1 <= edgeCost_i, edgeCost <= 10⁶</code>
- There are no repeated edges and no self-loops in the graph at any point.
- At most <code>100</code> calls will be made for <code>addEdge</code>.
- At most <code>100</code> calls will be made for <code>shortestPath</code>.

## Solution 1 - Dijkstra

class Graph:

    def __init__(self, n: int, edges: List[List[int]]):
        self.n = n
        self.adj = [[] for _ in range(n)]
        for a, nei, cost in edges:
            self.adj[a].append((nei, cost))

    def addEdge(self, edge: List[int]) -> None:
        a, nei, cost = edge
        self.adj[a].append((nei, cost))

    def shortestPath(self, node1: int, node2: int) -> int:
        heap = [(0, node1)]
        min_dist = [float("inf")] * self.n
        min_dist[node1] = 0
        
        while heap:
            dist, node = heapq.heappop(heap)
            if node == node2:
                return dist
            if dist > min_dist[node]:
                continue
            for nei, cost in self.adj[node]:
                new_dist = dist + cost
                if new_dist < min_dist[nei]:
                    min_dist[nei] = new_dist
                    heapq.heappush(heap, (new_dist, nei))
                    
        return -1


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

>### Complexity
>E = edge number of graph
>V = vertex number of graph
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(ElogV) | O(V + E) |

## Note
基本上Dijkstra的code就長這樣, 不太會因為題目而有更動, 所以如果把演算法理解後記下來, 對於以後算shortest path類型的題目幫助很大, Dijkstra比較困難的是Time Complexity與Space Complexity的分析, 這是Dijkstra的重點.

Reference
>[Pseudocode and Time Complexity Analysis](https://iq.opengenus.org/time-and-space-complexity-of-dijkstra-algorithm/)
>[Python & C++ Sample code](https://leetcode.com/problems/design-graph-with-shortest-path-calculator/solutions/3419976/c-java-python3-simple-dijkstra/?languageTags=python3)