在图上寻找最便宜路径，代价由使用节点的最大权值决定
我有一个图G，它有一个开始节点S和一个结束节点E。这个图的特殊之处在于，它不是边有代价，而是节点有代价。我想找到S和E之间的方式（一组节点，W)，使max（W）最小化。（实际上，我对W不感兴趣，只对max(W)感兴趣）等价地，如果我移除所有代价大于k的节点，那么最小的k是多少，这样S和E仍然是相连的？
我有一个想法，但想知道它是否正确和最佳。下面是我当前的伪代码：
L := Priority Queue of nodes (minimum on top)
L.add(S, S.weight)
while (!L.empty) {
X = L.poll()
return X.weight if (X == G)
mark X visited
foreach (unvisited neighbour N of X, N not in L) {
N.weight = max(N.weight, X.weight)
L.add(N, N.weight)
}
}
我相信最坏的情况是O（n log n)，其中n是节点数。
下面是我的特定问题（渗流）的一些细节，但我也对这个问题的一般算法感兴趣。节点权重在0和给定的最大值之间随机均匀分布。我的节点是泊松分布在R2平面上的，当两节点之间的距离小于给定常数时，两节点之间存在边。可能有很多节点，所以它们是动态生成的（隐藏在伪代码中的foreach中）。我的起始节点位于（0,0）中，结束节点是距离（0,0）大于R的任何节点。
编辑：节点上的权重是浮点数。
共有1个答案
从一个空图开始，您可以使用快速联合/查找数据结构，以增加权重的顺序一次插入一个顶点（以及它们到现有邻居的边），以维护连接组件的集合。这就像建立最小生成树的Kruskal算法一样，但不是一次增加一条边，而是对您处理的每个顶点v，您将组合v的所有邻居的分量。
您还可以跟踪哪两个组件包含起始顶点和结束顶点。（最初comp(S)=S和comp(E)=E；在每个联合操作之前，可以检查两个输入组件X和Y以查看其中一个是comp(S)还是comp(E)，后者在O(1)次中相应地更新。）一旦这两个组件变成单个组件（即comp(S)=comp(E))，您就停止了。刚刚增加的顶点是S和E之间的路径上的最大权值顶点，它使任意顶点的最大权值最小。
[编辑：添加时间复杂性信息]
如果图中包含n个顶点和m条边，则按权重对顶点进行排序需要O(n-log-n)时间。最多会有m个union操作（因为每个边都可以用来组合两个组件）。如果使用一个简单的不相交集数据结构，所有这些并运算可以在O(m+n，logn)时间内完成，这将成为总的时间复杂度；如果还使用了路径压缩，则会下降到O（m A(n))，其中A(n)是缓慢增长的逆阿克曼函数，但由于初始排序占主导地位，所以总体时间复杂度与以前保持不变。
假设权重为整数，Pham Trung的二分搜索方法需要O((n+m)log maxW）时间，其中maxW是图中最重的顶点。在稀疏图（其中m=O(n))上，这变成O(n log maxW)，而mine变成O(n log n)，所以在这里，如果log(maxW)<
-
我想找出面积最大的国家。 我的数据集如下 有人能帮我写mapreduce程序吗？ 我的映射器和缩减器代码如下 制图员 减速机
-
Dijkstra算法说 对于图中给定的源节点，算法找到该节点和其他节点之间的最短路径 我得到了算法来找到那个节点和其他节点之间的最短路径。但是我的问题是，如果我需要为Linkedin/facebook这样的大图找到两个特定节点（比如N1和N2）的最短路径，我需要计算该节点N1和领英上其他节点（用户，意味着十亿用户）之间的距离吗首先，将其存储在高速缓存中，然后在询问两个节点的最短距离时从高速缓存中返
-
我们知道在两个顶点之间寻找一条最大权重路径是NP难的。但是如果我们限制边缘权重，对于例如。所有边权值都小于某个特定值x。我清楚地定义下面的问题。 我有一个有向图G(V，E)，其中每条边的权值在1到V之间。我想在两个顶点u和V之间找到最大权值路径。
-
我正在上面的图上运行广度优先搜索，查找从到的最短路径。 我的代码 我需要追踪BFS ALGO通过的节点。遍历以到达节点6，如。为此，我创建了一个名为的列表&试图存储访问节点的前一个节点，以获得节点列表。转介
-
以下是消费税： 在某些图的问题中，顶点可以有权代替边的权或增加边的权。设Cv是顶点v的代价，C(x，y)是边(x，y)的代价。该问题涉及到在图G中寻找顶点a和顶点b之间的最便宜路径，路径的代价是该路径上遇到的边和顶点的代价之和。 (a)假设图中每条边的权重为零（而非边的代价为∞)，假设所有顶点1≤V≤n（即所有顶点的代价相同），Cv=1。给出一个求从a到b最便宜路径的高效算法及其时间复杂度。 (b
-
我需要为一组有向无环图找到从节点 0 开始的最长路径。我正在使用维基百科中的最长路径问题算法。我已经让算法适用于大多数图形，但对于其他图形，它没有给出正确的结果。算法为： 图形实现使用邻接列表来存储图形。如果我传递一个图，例如： 我得到的答案5，这是正确的。但是，如果我通过图表： 然后我得到2，而正确答案应该是3。 我使用的TopSort2算法是： DFS 算法包括：