问题标签 [weighted-graph]

我有一个包含 343 个节点和 4000 多个边的无向图。这些节点通过不同类型的关系相互连接。想象一下，我有 A、B、C、D、E 作为节点和 tie 1、tie 2 和 tie 3。我将数据框组织如下：

如上例所示，A 和 C 以及 A 和 B 已经相互链接了两次，无论它们的关系如何，也不管它们属于“node1”还是“node2”列。整个网络的这些重复次数之和为 4。

我完全想为我的图得到这个总和，它有 4000 多条边。查看特定节点/节点对的重复链接数量也很酷。希望我说得通

任何帮助真的很感激。

嗨，我在使用所选代码时遇到问题。谁能告诉我为什么粗体部分不起作用？

我正在阅读 LaFore 的数据结构和算法，我遇到了这本书提供的代码，它使用Dijkstra 算法来找到最短路径，是否也可以删除顶点或边？想知道为什么这本书没有包含删除方法吗？再次感谢任何帮助！

假设 e 是加权图中的一条边，它与顶点 v 相关，使得 e 的权重不超过与 v 相关的任何其他边的权重。证明存在包含该边的最小生成树。

我正在尝试找到一种算法，该算法可以找到给定树的最小总重量。

我得到一棵树和所有节点的权重（每个节点可以有不同的权重）。例如在此图中，每个节点的权重为 1： 具有权重的树

然后给我一组至少两个数字，我们称它们为 X。例如 X：2、3、4、5。每个节点分配一个 X 值，而相邻的两个节点不能有相同的 X 值。结果，每个节点的总权重为 X * weight。将所有节点的总权重相加后，我们就得到了树的总权重。 树结果

目标是找到一种算法，它可以找到 X 值的一个这样的分布，以便我们得到树的最小权重。

任何帮助，将不胜感激。

编辑：找到解决方案，这是找到最小最大瓶颈路线的工作算法。

所以这是我现在用 Python 编码的 dijkstra，但我不知道我应该如何修改它来计算最大重量最小的路线

我是 R 新手，这个问题很困扰我。我有一个加权和定向网络，我想做以下事情：

我有一个 igraph 网络。我想计算所有边的 edge_betweenness 并创建一个包含以下列的矩阵：

edgeID 指的是图中边的索引。我需要索引或 ID，因为我想在另一个矩阵中使用这个矩阵的元素。

所以谢谢你的帮助。

我有一个这样的加权有向图：

我想找到从开始到结束的最大成本路径的顶点列表。

在这个例子中，我应该得到：

我正在尝试使用此处找到的代码：

但我得到了错误：

我也试过这个java代码，但它只返回整数的最大总成本，我想要路径上顶点的名称。

有没有办法来解决这个问题？

我试图想出一个解决方案来找到使用 BFS 的无向加权图的单源最短路径算法。

我想出了一个解决方案，将每个边权重比如 x 转换为顶点之间的 x 边，每个新边的权重为 1，然后运行 ​​BFS。我会得到一棵新的 BFS 树，因为它是一棵树，所以从根节点到每个其他顶点只存在 1 条路径。

我遇到的问题是试图提出对以下算法的分析。每条边需要被访问一次，然后根据其权重分割成相应数量的边。然后我们需要找到新图的 BFS。

访问每条边的成本是 O(m)，其中 m 是边数，因为每条边都被访问一次以分割它。假设新图有 km 边（比如 m'）。BFS 的时间复杂度为 O (n + m') = O(n + km) = O(n + m) 即时间复杂度保持不变。给定的证明是否正确？

我知道我可以在这里使用 Dijkstra 算法，但我对分析这种基于 BFS 的算法特别感兴趣。

想知道这里是否有任何不正确的地方。我得到的唯一没有添加的建议是将矩阵填充到 integer.max_value。此外，权重必须是所有边的参数，当我们删除边时，权重变为 0，以防出现混淆。如果您发现任何不正确的地方，请告诉我（java）。