可以执行mssp(multiple source shortest path)的树，在很多论文中都说一定是embedded plannar graph。这是否意味着不能有相互重叠的边缘？如果可以的话
把这样的图变成平面图？
最佳答案
MSSP 的规范输入是 doubly connected edge list或类似的东西，它给出了图形的组合拓扑而不是几何图形。如果你有 straight-line graph那不是平面的(即它有交叉或重叠的边缘)，那么你需要以某种方式改变图形。一种可能性是在有交叉点的任何地方引入一个新顶点；另一种是删除有问题的边。
关于algorithm - 多源最短路径...嵌入平面图，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15806524/