更新图中的路径矩阵
Updating the matrix of paths in the graph
我有这个矩阵，它保持 vertexes.for 之间的路径，例如 4 个顶点，我们有这样的矩阵：
0 0 1 1
1 0 1 1
0 0 0 1
0 0 0 0
这表明我们有 (1,3) & (1,4) & (2,1) & (2,3) & (2,4) & (3,4) 之间的路径。
我的问题的输入是两个顶点之间的新路径，输出是该矩阵的更新。
例如：
输入：(3,2)
输出：
1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0
我想按这个顺序做：O(V^2)
N = 顶点数。
你有了新的优势：输入 (A,B)。
1 然后你遍历 B:
对于每个现有边 (B,X)，您都会得到一个（可能是新的）边 (A,X)
=> si N 操作
2 与 A 相同：
对于每个现有边 (Y,A)，您都会得到一个（可能是新的）边 (Y,B)
=> si N 操作
你对 X 和 Y（最多 2 N）做同样的事情。
3 对于每个 (Y,A) 和 (B,X)，
你添加 (Y,X)，所以 NxN 操作。
所以是 O(N^2)
我有这个矩阵，它保持 vertexes.for 之间的路径，例如 4 个顶点，我们有这样的矩阵：
0 0 1 1
1 0 1 1
0 0 0 1
0 0 0 0
这表明我们有 (1,3) & (1,4) & (2,1) & (2,3) & (2,4) & (3,4) 之间的路径。
我的问题的输入是两个顶点之间的新路径，输出是该矩阵的更新。
例如：
输入：(3,2)
输出：
1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0
我想按这个顺序做：O(V^2)
N = 顶点数。
你有了新的优势：输入 (A,B)。
1 然后你遍历 B: 对于每个现有边 (B,X)，您都会得到一个（可能是新的）边 (A,X) => si N 操作
2 与 A 相同： 对于每个现有边 (Y,A)，您都会得到一个（可能是新的）边 (Y,B) => si N 操作
你对 X 和 Y（最多 2 N）做同样的事情。
3 对于每个 (Y,A) 和 (B,X)， 你添加 (Y,X)，所以 NxN 操作。
所以是 O(N^2)