<分区>
有一个Dijkstra's algorithm .我想用给定的 |E| 和 |V| 生成图，其中算法执行最大松弛次数:alt ← dist[u] + length (u, v)。
这是一个ACM 问题。但我不知道如何解决它。我期待任何想法。
示例。让|V| = 4 和 |E| = 3。然后，我正在寻找具有以下边和权重的图 (v1, v2, w):
(1, 2, 0)
(1, 3, 1)
(1, 4, 2)
<分区>
有一个Dijkstra's algorithm .我想用给定的 |E| 和 |V| 生成图，其中算法执行最大松弛次数:alt ← dist[u] + length (u, v)。
这是一个ACM 问题。但我不知道如何解决它。我期待任何想法。
示例。让|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, 成本(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/