algorithm - 从顶点对创建图形，同时它们之间的距离最小

Question

我会这样写我的问题：

• 我有一个带有“空”顶点的无向图，但带有加权边（我们称之为距离）
• 另外，我有一对顶点的定向“填充”，例如，对 1->2 表示从包含一个的顶点到包含 2 的顶点。20->13 表示一对 2 个顶点，一个填充数字 20，另一个一个有 13 .. 等等
• 我可以将顶点的“填充”放置在图表中我想要的任何位置，而不是依赖于一对 - 对中的每个数字将仅象征一个顶点
• 每个顶点最多有 2 个出/入边，但可能有一对只有一个（所以，基本上，单）
• 会有循环

我想生成一个给定顶点对之间距离最短的图。

 One short and simple example

图形

             X---X---X
             |       |
             X----X--+

成对的 1->2 1->3 3->4 2->5 4->5

will produce something like

1---2---5
|       |
3----4--+

我知道这可以通过蛮力和 F-Warshal 算法来完成。问题是，如果没有更好的方法（对于 50 个顶点，有 50 个！组合 - 计算量很大）

再次感谢您的宝贵时间，如果，请提供更多答案 :) 祝您有美好的一天

标签： algorithmgraph-theorygraph-algorithm