前几天被问了道算法题，求思路

[Bryan0Z]

题目大概是这样的：
给定一张图，在图中增加若干个点和边，使得起点到到终点每条路径长度相同。示意图如下：


如图，左边路径到终点的距离为 3，右边路径距离为 2，因此应该在右边加一个节点，使得两边长度都为 3.

[twistoy]

没要求加的点和边数量最小的话就很简单啊，dfs 或者 bfs 找到所有起点到终点的路径。然后都照着最长的加就可以了

[PureWhiteWu]

两次 DFS：第一次求出最长路径，第二次加电和边。

[Bryan0Z]

@twistoy
@PureWhiteWu
我画的图例子比较简单，要是负责了，点和边加在哪里，怎么加都是问题

[takato]

可以删除边吗？不然这题没有意义啊。。。

[Bryan0Z]

@takato 为啥没意义呀

[pipapa]

bfs 若没有到达终点就一直加点和边，保证同时到达。是否可行？

[takato]

@Bryan0Z 如果不能删除，你的例子中，右路的最短路径永远是 2 或 2 以下。

[ihainan]

这种情况，如果出现环，路劲这一概念是怎么定义的…如果是按 1 - 2 - 4 和 1 - 2 - 3 - 4，那无论怎么添加都是无解呀……

[yemenchun1]

虽然不是最优解, 但是考虑下带深度限制的 dfs?

[vegito2002]

这题还是有点难的, 比如
1---2---3
| |
4----5

这种, 起点是 1, 终点是 3.
为了补全 1-2-3 这条路径的长度, 点到底加在哪里还是有点讲究: 如果加在 1-2 之间肯定不行;

更复杂一点都情况:
1---2---3---4---5
| / \ |
------6 8------

起点是 1, 终点是 5 这种, 所有路线都没有公共前缀或者后缀, 暂时没想到一个很系统的思路.

[vegito2002]

第一张图是: [1=[2], 2=[1,3,4], 3=[2,5], 4=[2,5], 5=[3,4]]
第二张图示: [1=[2,6], 2=[1,3], 3=[2,4,6,8], 4=[3,5], 5=[4,8], 6=[1,3], 8=[3,5]]
V 站为什么要把所有的空格都删了...

[Bryan0Z]

@vegito2002 因为默认是 markdown 格式

[Bryan0Z]

@ihainan 我也想到了，我觉得他的意思是同一个节点不能重复走，或者这是个有向图

[Bryan0Z]

@takato 我没表述清楚哈，可以在边的中间加一个点，改变路径长度

[twistoy]

@Bryan0Z 首先，通过一次 dfs 求出来最大深度，也就是添加完边之后的期望深度。
这个问题就变成了给一个指定点，希望起点到这个点的所有路径的长度都是 N。
然后每个指定点的每个前驱，我们都会有一个深度的期望，这个问题就和原问题一样了，可以递归完成。
那对于每个点，它的不同后继会给它一个不同的深度期望，这个时候应该取最小的那个期望，作为它真正的深度期望，因为更深的期望可以通过在这个点和后继之间加边来完成。
大概这样。。。