问多源最短path...Embeded平面图
EN

Stack Overflow用户

提问于 2013-04-04 16:49:43

回答 1查看 208关注 0票数 2

多源最短路径(multiple source shortest path，mssp)可以在其上执行的树，在许多文献中都指出它一定是嵌入平面图。这是否意味着不能有相互重叠的边？如果是这样的话是可能的

把这样的图变成平面图？

algorithm

shortest-path

回答 1

Stack Overflow用户

回答已采纳

发布于 2013-04-04 20:42:49

MSSP的规范输入是一个doubly connected edge list或类似的东西，它给出了图的组合拓扑，但不是几何。如果你有一个不是平面的straight-line graph (即，它有交叉或重叠的边)，那么你需要以某种方式改变图形。一种可能是在有交叉点的地方引入一个新的顶点；另一种是删除有问题的边。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/15806524

复制

相似问题

问多源最短path...Embeded平面图
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问多源最短path...Embeded平面图EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问多源最短path...Embeded平面图
EN