graph - 如果添加新顶点，如何重新计算加权无向图的所有对最短路径？(How to recompute all pair shortest path of a weighted undirected graph if a new vertex is added?)

Question

I have a graph G(V,E).

(我有一个图G（V，E）。)

I computed the shortest paths for all pairs of vertices using Floyed-Warshall algorithm.

(我使用Floyed-Warshall算法计算了所有顶点对的最短路径。)

Now, say a new vertex v is added to the graph.

(现在，说一个新的顶点v被添加到图中。)

some new edges which connect v to some other pre existing vertices are also newly added.

(还新增了一些将v连接到其他现有顶点的新边。)

Now, how to recompute the all pairs shortest paths again?

(现在，如何再次重新计算所有对的最短路径？)

  ask by Cradle Faith translate from so

Answer 1

等待大神答复