考虑一个在每个节点上而不是在两个节点之间都有权重的图。因此，前往一个节点的成本将是该节点的权重。
1-我们如何表示这个图？
2- 这种类型的图是否有最小生成路径算法（或者我们可以修改现有算法）？
例如，考虑一个矩阵。什么路径，当从某个数字到另一个数字时，会产生最小和？（请记住，图表必须是有向的）
问问题
152 次
1 回答
0
如果不想调整现有算法并使用面向边缘的方法，可以将节点权重转换为边缘权重。对于节点 v 的每个传入边，将 v 的权重保存到边上。这就是代表。
好吧，使用 1 的方法。现在，使用 MST 等众所周知的算法很容易做到这一点。
您还可以根据需要表示图形并在节点处保持权重。该算法根本没有使用Weight w = edge.weight();它会使用Weight w = edge.target().weight()
简单的完成。不需要大的调整。
如果必须使用邻接矩阵，则需要第二个具有节点权重的数组，并且在邻接矩阵中只有 0 - 表示没有边或 1 - 表示边。
希望有帮助
于 2012-09-18T07:56:19.110 回答