algorithm - 多源最短路径...嵌入式平面图

Question

可以在其上执行 mssp（多源最短路径）的树在许多论文中都指出它必须是嵌入式平面图。这是否意味着不能有相互重叠的边缘？如果可以，可以将此类图更改为平面图吗？

Answer 1

MSSP 的规范输入是一个双向连接的边列表或类似的东西，它给出了图形的组合拓扑，而不是几何。如果您有一个不是平面的直线图（即，它有交叉或重叠的边），那么您需要以某种方式更改该图。一种可能性是在有交叉点的地方引入一个新顶点；另一个是删除有问题的边缘。