algorithm - 如何生成具有最大松弛度的图形？

Closed. This question needs to be more focused 。它目前不接受答案。












想改善这个问题吗？更新问题，使其仅通过 editing this post 关注一个问题。

12 个月前关闭。



Improve this question




有一个 Dijkstra's algorithm 。我想用给定的 |E| 和 |V| 生成图形，其中算法执行最大次数的松弛: alt ← dist[u] + length(u, v) 。

这是一个 ACM problem 。但我不知道如何解决它。我期待着任何想法。
Example 。让 |V| = 4 和 |E| = 3 。然后，我寻找具有以下边和权重的图( v1, v2, w ):
(1, 2, 0)(1, 3, 1 )
(1, 4, 2 )

最佳答案

这看起来可能有用，虽然我还没有考虑太多。

添加边 (1, 2, 1); (1, 3, 2); ...; (1, N, k) 。

如果没有完成，添加边 (2, 3, cost(1, 3) - 2); (2, 4, cost(1, 4) - 2); ...
如果没有完成，添加边 (3, 4, cost(1, 4) - 3); ...
依此类推，直到完成。

您的图表将如下所示:

 4---------------
 |        \     |
 |         |    |
(3)       (1)   |
 |         |    |
 |         |    |
 1 --(1)-- 2   (0)
 |         |    |
 |         |    |
(2)       (0)   |
 |         |    |
 |        /     |
 3---------------

首先，该算法将放松所有连接到节点 1 的节点:

d[4] = 3
d[2] = 1
d[3] = 2

然后，所有连接到节点 2 的节点:

d[3] = 1
d[4] = 2

然后所有连接到节点 3 的

d[4] = 2

所以我们做了 6 松弛:每条边一个。这是最大可能。

关于algorithm - 如何生成具有最大松弛度的图形？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28920645/