图最短路径？

Question

我正面对的是我认为的图形上最短路径问题。

我需要找到从节点A到B的最短路径，因为所有的边都对连接的顶点有正的权重，∞对于没有连接的顶点。

顶点具有可变的正面权重。

考虑路径中涉及的所有顶点，路径的代价是具有最大权重的顶点的权重。

我应该在这种情况下应用Dijkstra吗？如果是的话，考虑到每个顶点的权重根据以前访问过的顶点而变化？

你能指出我如何解决这个问题吗？

Answer 1

我不能理解你是否应该考虑边缘的权重，因为你说你希望顶点上的最大/最小权重的路径从A到B. 我的解决方案是将每个顶点上的权重，到边上的权重，就像在图像中一样：

现在您想要找到从A到B的路径，其中边缘上的最大权重是最小/最大值。 您可以使用MST algotirhm，因为您不关心路径长度，而只关注最大/最小边缘成本。