有向加权边图及其权值的算法
我有一个有向图，边上的权值是非负的。
我的算法应该做到以下几点：
- 获取从顶点u到顶点V的所有路径
- 计算从u到v的每条路径上的最小加权边
- 计算我从上面计算的最小加权边的最大值。
共有1个答案
我想我们这里不需要dijkstra。假设我们选择了具有最小边的路径。它显然不包括权重较小的边缘。所以算法是
- 选择
k最重边 - 使用dfs/bfs检查
v是否可以从u通过此边到达(f(K)为真) - 如果
K1>K2和f(K2)为真，那么显然f(K1)为真 - 所以我们可以在
k上运行二进制搜索
时间复杂度为O((n+M)log M)，其中n-顶点数和M-边数
-
给我一个图中名为“a”的顶点，对于v中的每一个v，我需要找到从a到v的路径的权重，它在时间O(v+E)中权重最低。我不得不只使用BFS或DFS（尽管这很可能是BFS的问题）。 我想过要制作一个新的图，其中边为0的顶点是统一的，然后在它上面运行BFS，但是这会破坏图的方向（如果图是无向的或者权重是{2,1}，对于边为2，我会创建一个新的顶点）。 如果有任何帮助，我将不胜感激。 谢谢
-
我正在学习最小生成树。我研究了Prim的加权有向图算法。 算法简单 您有两组顶点：已访问和未访问 将所有边的距离设置为无穷远 从未访问集合中的任意顶点开始并探索其边 在所有边中，如果目标顶点没有被访问，并且如果边的权重小于目标顶点的距离，则用该边的权重更新目标顶点的距离 选择距离最小的未访问顶点，然后再进行一次，直到所有顶点都访问完 相信通过以上算法，能够在所有的生成树中找到代价最小的生成树，即最
-
假设我们有一个有向图，它同时包含正加权边和负加权边。 我知道最短路径解决方案是Bellman-Ford算法。 我的问题是：为什么我们不能只是在所有的边成本上增加一些大的值N，这样就不再有负边了，然后使用效率高得多的Dijkstra算法？
-
问题内容： 使用Redis实现加权图的最佳方法是什么？ 我们将主要在图上搜索最短路径（可能使用Dijkstra算法） 目前我们考虑将边缘添加到Redis 对于每个节点，我们将使用nodeId作为键，并使用引用节点的键的sortedset，sortedSet中每个nodeId的分数就是边缘的权重。 你怎么看？如果我错了，请纠正我，但这里唯一的遗憾是，对于sortedset中的下一个节点的每个查询，我
-
给定一个节点和边的加权无向图。边缘权重（整数）最大可达。存在查询。每个查询给出两个节点和一个整数绑定的。如果和之间存在路径，使得路径中的每个边权重都是，那么回答是else。 请注意，路径不一定要最短。路径上的最大权重是。天真的方法当然是行不通的。如何快速回答查询（在O(n，lg，n)或类似的情况下）？
-
B）设是带有向图（无环多边）的一个邻接矩阵，其中是边到的一个权重。如果没有这样的边并且对于evrey我们有。矩阵。槽表示什么？最小权重？还是...？ 知道吗？ 编辑：我的意思是这些算法在图中找到哪一个？找到最大重量？最小重量？什么也没找到？