这是许多现有算法的细微变化，拓扑排序似乎是最明显和最有效的答案。
让我们举个例子来更清楚地解释我的意思。
我有一个 DAG，从顶点 A 开始，有 5 个顶点/节点到 E。我想找到从 A 到 E 的最短路径，这样每个节点本身都随路径加权，在某些时候每个节点都有可能节点可以有超过 1 个加权值。节点可以有许多变量，例如 x、y 和 z。这些输入基于某些偏好(例如用户偏好)进行加权。所以 y 可以比 x 或 z 更重，这考虑到“更短”的路径。
我附上了一张图片来解释我想做什么。实现这一目标的最佳方式是什么？向节点添加权重的原因是给定输入对特定节点的偏好。
在饼图中，我们可以看到 Y 的权重最高，偏好为 50%，因此我们将 Y*N，其中 N 是计算权重的数字。在所附图表的 D 中，x, y z 将为 {1, 0.6, 0.3}
编辑:根据原答案，更新描述。简化了图表并添加了一个新的饼图来解释权重。
最佳答案
使用有向图可以很容易地处理节点上的权重。常见的做法如下:
- 将每个节点V拆分为两个节点V'和V"
- 添加一条从V'到V"的边，其权重等于节点的权重
- 对于每个入站边 (U, V) 在图中添加一条从 U"到 V' 的具有相同权重的新边
- 对于每条出站边 (V, T) 在图中添加一条从 V"到 T' 的具有相同权重的新边
现在您已将问题简化为“常规”DAG 中的最短路径问题，您应该知道如何解决它。
不清楚你的问题中的多个权重是什么意思，但有两种选择:
- 如果您的意思是您可以选择节点处的任何权重，只需在添加边 V'->V"时使用最小的权重即可
- 如果权重是累加的，在添加边V'->V"的时候简单相加
关于java - Java中顶点/节点权重的DAG最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48648823/