graph - 图最短路径？

Question

我面临着我认为是图上的一种最短路径问题。

我需要找到从节点 A 到 B 的最短路径，考虑到所有边对连接的顶点具有正权重，对于未连接的顶点具有 ∞。

顶点具有可变的正权重。

考虑到该路径中涉及的所有顶点，路径的成本是具有最大权重的顶点的权重。

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

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

Answer 1

我不明白你是否应该考虑边缘的权重，因为你说你想要一个顶点上可能具有最大/最小权重的路径，从 A 到 B。我的解决方案是将顶点上的每个权重转换为边缘的重量，就像在图像中一样：

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