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.
Solutions
Solution 1: Dijsktra's Algorithm
In the initialization function, we first use the adjacency matrix $g$ to store the edge weights of the graph, where $g_{ij}$ represents the edge weight from node $i$ to node $j$. If there is no edge between $i$ and $j$, the value of $g_{ij}$ is $\infty$.
In the addEdge function, we update the value of $g_{ij}$ to $edge[2]$.
In the shortestPath function, we use Dijsktra's algorithm to find the shortest path from node $node1$ to node $node2$. Here, $dist[i]$ represents the shortest path from node $node1$ to node $i$, and $vis[i]$ indicates whether node $i$ has been visited. We initialize $dist[node1]$ to $0$, and the rest of $dist[i]$ are all $\infty$. Then we iterate $n$ times, each time finding the current unvisited node $t$ such that $dist[t]$ is the smallest. Then we mark node $t$ as visited, and then update the value of $dist[i]$ to $min(dist[i], dist[t] + g_{ti})$. Finally, we return $dist[node2]$. If $dist[node2]$ is $\infty$, it means that there is no path from node $node1$ to node $node2$, so we return $-1$.
The time complexity is $O(n^2 \times q)$, and the space complexity is $O(n^2)$. Where $n$ is the number of nodes, and $q$ is the number of calls to the shortestPath function.
classGraph:def__init__(self,n:int,edges:List[List[int]]):self.n=nself.g=[[inf]*nfor_inrange(n)]forf,t,cinedges:self.g[f][t]=cdefaddEdge(self,edge:List[int])->None:f,t,c=edgeself.g[f][t]=cdefshortestPath(self,node1:int,node2:int)->int:dist=[inf]*self.ndist[node1]=0vis=[False]*self.nfor_inrange(self.n):t=-1forjinrange(self.n):ifnotvis[j]and(t==-1ordist[t]>dist[j]):t=jvis[t]=Trueforjinrange(self.n):dist[j]=min(dist[j],dist[t]+self.g[t][j])return-1ifdist[node2]==infelsedist[node2]# Your Graph object will be instantiated and called as such:# obj = Graph(n, edges)# obj.addEdge(edge)# param_2 = obj.shortestPath(node1,node2)
classGraph{privateintn;privateint[][]g;privatefinalintinf=1<<29;publicGraph(intn,int[][]edges){this.n=n;g=newint[n][n];for(varf:g){Arrays.fill(f,inf);}for(int[]e:edges){intf=e[0],t=e[1],c=e[2];g[f][t]=c;}}publicvoidaddEdge(int[]edge){intf=edge[0],t=edge[1],c=edge[2];g[f][t]=c;}publicintshortestPath(intnode1,intnode2){int[]dist=newint[n];boolean[]vis=newboolean[n];Arrays.fill(dist,inf);dist[node1]=0;for(inti=0;i<n;++i){intt=-1;for(intj=0;j<n;++j){if(!vis[j]&&(t==-1||dist[t]>dist[j])){t=j;}}vis[t]=true;for(intj=0;j<n;++j){dist[j]=Math.min(dist[j],dist[t]+g[t][j]);}}returndist[node2]>=inf?-1:dist[node2];}}/** * 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); */
classGraph{public:Graph(intn,vector<vector<int>>&edges){this->n=n;g=vector<vector<int>>(n,vector<int>(n,inf));for(auto&e:edges){intf=e[0],t=e[1],c=e[2];g[f][t]=c;}}voidaddEdge(vector<int>edge){intf=edge[0],t=edge[1],c=edge[2];g[f][t]=c;}intshortestPath(intnode1,intnode2){vector<bool>vis(n);vector<int>dist(n,inf);dist[node1]=0;for(inti=0;i<n;++i){intt=-1;for(intj=0;j<n;++j){if(!vis[j]&&(t==-1||dist[t]>dist[j])){t=j;}}vis[t]=true;for(intj=0;j<n;++j){dist[j]=min(dist[j],dist[t]+g[t][j]);}}returndist[node2]>=inf?-1:dist[node2];}private:vector<vector<int>>g;intn;constintinf=1<<29;};/** * 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); */
constinf=1<<29typeGraphstruct{g[][]int}funcConstructor(nint,edges[][]int)Graph{g:=make([][]int,n)fori:=rangeg{g[i]=make([]int,n)forj:=rangeg[i]{g[i][j]=inf}}for_,e:=rangeedges{f,t,c:=e[0],e[1],e[2]g[f][t]=c}returnGraph{g}}func(this*Graph)AddEdge(edge[]int){f,t,c:=edge[0],edge[1],edge[2]this.g[f][t]=c}func(this*Graph)ShortestPath(node1int,node2int)int{n:=len(this.g)dist:=make([]int,n)fori:=rangedist{dist[i]=inf}vis:=make([]bool,n)dist[node1]=0fori:=0;i<n;i++{t:=-1forj:=0;j<n;j++{if!vis[j]&&(t==-1||dist[t]>dist[j]){t=j}}vis[t]=trueforj:=0;j<n;j++{dist[j]=min(dist[j],dist[t]+this.g[t][j])}}ifdist[node2]>=inf{return-1}returndist[node2]}/** * Your Graph object will be instantiated and called as such: * obj := Constructor(n, edges); * obj.AddEdge(edge); * param_2 := obj.ShortestPath(node1,node2); */
classGraph{privateg:number[][]=[];privateinf:number=1<<29;constructor(n:number,edges:number[][]){this.g=Array.from({length:n},()=>Array(n).fill(this.inf));for(const[f,t,c]ofedges){this.g[f][t]=c;}}addEdge(edge:number[]):void{const[f,t,c]=edge;this.g[f][t]=c;}shortestPath(node1:number,node2:number):number{constn=this.g.length;constdist:number[]=newArray(n).fill(this.inf);dist[node1]=0;constvis:boolean[]=newArray(n).fill(false);for(leti=0;i<n;++i){lett=-1;for(letj=0;j<n;++j){if(!vis[j]&&(t===-1||dist[j]<dist[t])){t=j;}}vis[t]=true;for(letj=0;j<n;++j){dist[j]=Math.min(dist[j],dist[t]+this.g[t][j]);}}returndist[node2]>=this.inf?-1:dist[node2];}}/** * 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) */
publicclassGraph{privateintn;privateint[,]g;privatereadonlyintinf=1<<29;publicGraph(intn,int[][]edges){this.n=n;g=newint[n,n];for(inti=0;i<n;i++){for(intj=0;j<n;j++){g[i,j]=inf;}}foreach(vareinedges){intf=e[0],t=e[1],c=e[2];g[f,t]=c;}}publicvoidAddEdge(int[]edge){intf=edge[0],t=edge[1],c=edge[2];g[f,t]=c;}publicintShortestPath(intnode1,intnode2){int[]dist=newint[n];bool[]vis=newbool[n];Array.Fill(dist,inf);dist[node1]=0;for(inti=0;i<n;++i){intt=-1;for(intj=0;j<n;++j){if(!vis[j]&&(t==-1||dist[t]>dist[j])){t=j;}}vis[t]=true;for(intj=0;j<n;++j){dist[j]=Math.Min(dist[j],dist[t]+g[t,j]);}}returndist[node2]>=inf?-1:dist[node2];}}/** * 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); */