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.
這裡有一個有方向且帶有權重的圖，它包含了 n 個節點，節點編號從 0 ~ n - 1。 圖中的邊(edges)一開始由給予的陣列 edges 來表示，其中 edges[i] = [fromi, toi, edgeCosti]， 代表從節點 fromi 指向節點 to_i，且該邊的成本為 edgeCosti。 請實作 Graph class: Graph(int n, int[][] edges) 初始化一個有 n 個節點和給予邊的物件。 addEdgge(int[] edge) 將一條新的邊新增到圖中，該邊的格式為 [from, to, edgeCost]， 並保證在新增這條邊之前，這兩個節點之間不存在任何的邊。 shortestPath(int node1, int node2) 回傳從 node1 到 node2 的最小路徑成本， 如果不存在任何可到達的路徑，則回傳 -1。 路徑成本為路徑中所有邊的權重總和。
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.
Solution:
我們先在 Graph class 裡面建立 private 的 n(0 ~ n -1 個節點數量)，
以及 dis(distance) 的數值陣列。
接著我們建立一個 n x n 的陣列，初始值假設為最大的安全值，
以及 dis 中自己到自己的距離為 0，接著就可以把例子中的初始陣列填入，
我們透過 Floyd-Warshall 對每個節點檢查最短的路徑，
這樣就完成了我們的 constructor。
在建立 addEdge 時，我們需要新增一條邊 from -> to (cost)，
因為我們建構子時有跑過最短的距離，所以 dis[i][from] 與 dis[to][j] 再加上 cost，
就可以和原有的 dis[i][j] 比較取最小值。
再來就是 shortestPath() 的部分，我們從 dis 讀出 node1 -> node2。
如果是 INF ，則回傳 -1，表示不可達到，如不是 INF，則回傳距離。
Code 1: BigO(n ^ 3)
class Graph {
private n: number;
private dis: number[][];
constructor(n: number, edges: number[][]) {
const INF = Infinity;
this.n = n;
this.dis = Array.from({length: n}, () => Array(n).fill(INF));
for (let i = 0; i < n; i++) {
this.dis[i][i] = 0;
}
for (const edge of edges) {
const [from, to, cost] = edge;
this.dis[from][to] = Math.min(this.dis[from][to], cost);
}
// Floyd-Warshall
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) {
this.dis[j][k] = Math.min(this.dis[j][k], this.dis[j][i] + this.dis[i][k]);
}
}
}
}
addEdge(edge: number[]): void {
const INF = Infinity;
const [from, to, cost] = edge;
for (let i = 0; i < this.n; i++) {
for (let j = 0; j < this.n; j++) {
this.dis[i][j] = Math.min(
this.dis[i][j],
this.dis[i][from] + cost + this.dis[to][j]
);
}
}
}
shortestPath(node1: number, node2: number): number {
const INF = Infinity;
return this.dis[node1][node2] === INF ? -1 : this.dis[node1][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)
*/
FlowChart:
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]] Initial distance matrix: Node0 Node1 Node2 Node3 Node0 0 2 5 INF Node1 INF 0 1 INF Node2 INF INF 0 INF Node3 3 INF INF 0 After considering node 0 as intermediate: Node0 Node1 Node2 Node3 Node0 0 2 5 INF Node1 INF 0 1 INF Node2 INF INF 0 INF Node3 3 5 8 0 After considering node 1 as intermediate: Node0 Node1 Node2 Node3 Node0 0 2 3 INF Node1 INF 0 1 INF Node2 INF INF 0 INF Node3 3 5 6 0 After considering node 2 as intermediate: Node0 Node1 Node2 Node3 Node0 0 2 3 INF Node1 INF 0 1 INF Node2 INF INF 0 INF Node3 3 5 6 0 After considering node 3 as intermediate: Node0 Node1 Node2 Node3 Node0 0 2 3 INF Node1 INF 0 1 INF Node2 INF INF 0 INF Node3 3 5 6 0 After adding edge [1,3,4]: Node0 Node1 Node2 Node3 Node0 0 2 3 6 Node1 7 0 1 4 Node2 INF INF 0 INF Node3 3 5 6 0