algorithm - 加权有向无环图 : algorithm to find edge weights such that they define a distance function?

Question

我有一个可以用有向无环图 (DAG) 表示的技术问题。节点代表事件(时间未知)，有向边编码关系:“我比你年轻/我发生在你之前”。

我需要估计边权重(即“动态权重”)，以便加权 DAG (WDAG) 暗示 DAG 上的距离函数。换句话说，节点 A 和 B 之间路径的权重总和对于所有路径都应该相等。

这是一个未确定的问题，即使权重是整数(我想这与拓扑排序不唯一的潜在原因相同)。一般来说，表示节点/事件之间的时间间隔的边权重是实数。因此，我在加权 DAG 上引入了一些预设目标函数 C=J(WDAG)，此处未指定。

我的问题是:是否有一种算法可以在 WDAG 上分配正定权重，受约束 1) 权重形成 DAG 的距离函数和 2) 最小化目标函数成本 C。

这似乎与通常与 WDAG 相关的最短路径或最小生成树问题无关。对于上述问题的正式或启发式解决方案有什么想法吗？

问候，

史蒂芬

Answer 1

我想你只需要 topological sorting .

1. 根据拓扑排序对节点进行排序。
2. 按照你得到的顺序将它们分布在 [0,1] 区间内。
3. 现在 [0,1] 线上节点对的距离将为您提供连接它们的边的权重。

这是一种可能的解决方案。如果您对权重的限制比您在问题中描述的更多，则问题可能会更难。