如何生成最大放松的图形？

Question

有一个Dijkstra的算法.我想给生成图形|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)

Answer 1

这看起来可能有用,虽然我还没有多想.

添加边缘(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放松:每个边缘一个.这是最大可能的.