4

假设我有一个节点图（网络），权重如下： 1. 在两个节点之间的链接上单向行驶。2. 在两个节点之间的链接上以另一种方式行驶（这些可能不同）。3. 从一个链接更改为另一个链接。

此外，一些节点只是单向的。

在这种情况下，什么是最好的算法：a）找到最小生成树 b）找到两个节点之间的最短路径 c）找到“旅行推销员”路径（即，最短的路径去任何地方，重复最少） ?

另外，最好将双向事物视为两条单向路径，而不是在每个方向具有不同权重的双向路径？

- -一个例子 - -

              3
  A --<2/3>-- B --<3/2>-- C
  | 1        2|3
  |           |
  ^1/4       ^4/3
  |           |
  |3         4|
8 D --<3/5>-- E
  |2
  |
1 ^3/1
  |
  |
  F

其中 <2/3> 表示 2 左行和 3 右行的重量。^1/4 表示 1 上行和 4 下行。两个链接之间的单个数字是更改链接的成本 - 例如，从 AD 到 DF 成本为 8，从 AB 到 BE 成本为 2。

希望这是有道理的...

西蒙

（ps 为不好的术语道歉 - “链接”，“边缘” - 无论你喜欢什么;））

为了更好地解释权重类型，假设边缘是火车轨道，节点是车站。边缘的成本是火车在两个车站之间的行程时间，节点的成本是换乘时间的长短（即使在同一节点，边缘之间也可能有所不同，具体取决于站台的距离，服务的定期性等）。

4

2 回答 2

4

是的，将它们视为两条而不是一条。然后你可以毫无问题地使用传统的图论算法，特别是如果你总是保证在每个方向都有权重。如果您只是使用我刚刚帮助您创建的“正常”图表，这些算法很容易找到。

您可以使用Dijkstra 的最短路径。

您可以Prim 的最小生成树。

你可以用谷歌搜索非对称 TSP 来尝试找到一个算法，我很确定算法简介也有这方面的内容。抱歉，我无法为您找到一个好的实现。这里还有几个关于非对称 TSP 的好问题，现在您知道它被称为非对称 TSP。

祝你好运！我喜欢图论。

-Brian J. Stinar-

于 2011-04-26T23:35:54.377 回答
2

对于您的“交换”权重，您可以制作一个小子图来对它们进行编码。例如，您有：

  |   
  |3  
8 D --
  |2
  |

您可以仅使用边缘上的权重对其进行编码，如下所示：

  |
  |
  D0
  | \3
  |  \
 8|   D2--
  |  /
  | /2
  D1
  |
  |

请注意，您不必使用 8 边从 D0 到 D1，因为您可以使用 D0->D2->D1 来代替权重 5。我不确定您的原始配方是否允许这样做。

于 2011-04-28T18:17:36.527 回答