0

我们必须在图中找到从源到汇的路线，其中最大成本边和最小成本边之间的差异最小。

我尝试使用递归解决方案，但它会在循环条件下失败，并且修改后的 dijkstra 也失败了。

有没有一种算法我不必找到所有路线然后找到最小值？

4

2 回答 2

1

按权重对边进行排序（按非递减顺序），然​​后为每个边执行下一个：添加下一条边（按非递减顺序权重更大或相等的边），直到源和接收器连接，然后更新您的回答最后一个边缘之间的差异，如下所示：

    ans = INFINITE
    for each Edge e1 in E (sorted by weight in non-decreasing order)
        clear the temporal graph
        for each Edge e2 in E
            if e2.weight >= e1.weight  
                add e2 to the temporal graph
                if sink and source are connected in the temporal graph
                    ans = min(ans, e2.weight - e1.weight)
                    break
    print ans

如果您使用 UNION-FIND 结构添加边并检查源和接收器之间的连通性，您应该得到 O(edges^2) 的总时间

于 2017-08-08T03:25:40.797 回答
-1

好的，所以您有一个图，并且您需要找到从一个节点（源）到另一个节点（接收器）的路径，以使路径上的最大边权重减去路径上的最小边权重最小化。你没有说你的图是有向的，可以有负边权重，还是有循环，所以让我们假设所有这些问题的答案都是“是”。

在计算您的路径“分数”（边缘权重之间的最大差异）时，我们观察到这些类似于路径距离：您可能有一条从 A 到 B 的路径得分更高（不受欢迎）或更低（合意）。如果我们将路径分数视为路径权重，我们观察到，当我们通过添加新边来构建路径时，路径分数（=权重）只会增加：给定路径 A->B->C，其中权重（A->B） =1且权重（B->C）=5，路径得分为4，如果我将边C->D添加到路径A->B->C，路径得分只能增加或保持不变：最小边重和最大边重之差不小于4。

所有这一切的结论是，我们可以探索图寻找最佳路径，就好像我们正在寻找没有负边的图中的最佳路径一样。但是，可能存在（并且可能存在，鉴于所描述的连接性）循环。这意味着Dijkstra 的算法，如果正确实现，将具有相对于我们今天所知道的该图的拓扑结构的最佳性能。

没有全图探索就没有解决方案

人们可能会误以为我们可以在不探索整个图的情况下就哪条边应该属于最佳路径做出局部良好的决策。下面的子图说明了这个问题：

在此处输入图像描述

假设您需要一条从 A 到 F 的路径，并且您位于节点 B。鉴于您所知道的一切，您会选择一条到 C 的路径，因为它可以最小化路径分数。你（还）不知道的是，该路径中的下一条边将导致该路径的分数大幅增加。如果您知道您会选择边 B->D 作为最佳路径中的下一个元素。

于 2013-04-02T04:38:32.087 回答