双向图算法
假设我有一个节点图（网络），其权重如下： 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 为不好的术语道歉 - “链接”， “边缘” - 无论你喜欢什么；））
为了更好地解释加权类型，想象边缘是火车轨道，节点是车站。边缘上的成本是火车在两个车站之间的行程时间，节点上的成本是换乘时间有多长（即使在同一节点，边缘之间也可能有所不同，具体取决于站台的距离有多远，服务的定期程度等）。
Say I have a graph (network) of nodes, with weightings on the following:
1. travelling one way on a link between two nodes.
2. travelling the other way on a link between two nodes (these might be different).
3. changing from one link to another.
Also, some of the nodes are one-way only.
In this case, what would be the best algorithms for:
a) finding a minimum spanning tree
b) finding the shortest route between two nodes
c) finding the "travelling salesman" path (i.e. the shortest route that goes everywhere, with minimum duplication)?
Also, would it be best to treat the bi-directional thing as two single-directional paths, rather than a bidirectional path with different weightings in each direction?
---an example---
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
Where <2/3> means weight of 2 travelling left and 3 travelling right.
^1/4 means 1 travelling up and 4 travelling down. A single number between two links is the cost of changing links - e.g to go from AD to DF costs 8, and from AB to BE costs 2.
Hope that makes sense...
Simon
(p.s apologies for bad terminology - "links", "edges" - whatever you like ;) )
To try and explain the types of weighting better, imagine the edges are train tracks, and the nodes are stations. The cost on the edge is the journey time on a train between two stations, and the costs on the nodes are how long the interchange time is (which may vary between edges even at the same node, depending on how far away the platform is, how regular the service is, etc).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
是的，将它们视为两条边而不是一条。然后，您可以毫无问题地使用传统的图论算法，特别是如果您始终保证每个方向都有权重。如果您只是使用我刚刚帮助您创建的“正常”图表，那么这些算法很容易找到。
您可以使用 Dijkstra's 作为最短路径。
您可以使用 Prim 来获取最小生成树。
您可以通过 Google 搜索非对称 TSP 来尝试找到一种算法，我很确定算法简介也有这方面的内容。抱歉，我无法为您找到该方案的良好实现。这里还有一些关于非对称 TSP 的好问题，现在您知道它被称为非对称 TSP。
祝你好运！我喜欢图论。
-布莱恩·J·斯蒂纳尔-
Yes, treat these as two edges instead of one. Then you can use traditional graph theory algorithms on this without a problem, especially if you are always guaranteed to have weights in each direction. These algorithms are easy to find if you are just using a 'normal' graph like I have just helped you create.
You can use Dijkstra's for shortest path.
You can Prim's for a minimum spanning tree.
You can Google for the asymmetric TSP to try and find an algorithm for that, and I'm pretty sure the Introduction to Algorithms has something on this too. Sorry I couldn't find a good implementation of that one for you. There are also a couple of good questions on here about the asymmetric TSP, now that you know it's called the asymmetric TSP.
Good luck! I love graph theory.
-Brian J. Stinar-
对于您的“交换”权重，您可以制作一个小子图来对它们进行编码。例如，您可以：
您可以仅使用边上的权重对其进行编码，如下所示：
只需注意您不必使用 8 条边即可从 D0 到 D1，因为您可以使用 D0-> ;D2->D1，权重为 5。我不确定你原来的配方是否允许这样做。
For your "interchange" weights, you can make a little subgraph to encode those. For example, you have:
You can encode that using just weights on edges, like this:
Just watch out for the fact that you don't have to use the 8 edge to get from D0 to D1, as you can go D0->D2->D1 for a weight of 5 instead. I'm not sure if that is allowed in your original formulation.