我面对的是我认为是图表上的一种最短路径问题 .
我需要找到从节点A到B的最短路径，考虑到所有边缘对于连接的顶点具有正权重，对于未连接的顶点具有∞ .
顶点具有可变的正重量 .
考虑到该路径中涉及的所有顶点，路径的成本是具有最大权重的顶点的权重 .
我应该在这种情况下应用Dijkstra，如果是这样的话，考虑到每个Vertex的权重会根据之前访问的顶点而变化吗？
你能指点我怎么解决这个问题吗？
我不明白你是否应该考虑边缘的权重，因为你说你想要一个顶点上最大/最小权重的路径，从A到B.我的解决办法是将顶点上的每个权重转换为边缘的重量，就像在图像中一样：
现在你想要找到从A到B的路径，其中边缘上的最大权重是min / max . 你可以使用MST algotirhm，因为你不关心路径长度，而只关心最大/最小边缘成本 .
1 回答
我不明白你是否应该考虑边缘的权重，因为你说你想要一个顶点上最大/最小权重的路径，从A到B.我的解决办法是将顶点上的每个权重转换为边缘的重量，就像在图像中一样：
现在你想要找到从A到B的路径，其中边缘上的最大权重是min / max . 你可以使用MST algotirhm，因为你不关心路径长度，而只关心最大/最小边缘成本 .