问题标签 [weighted-graph]

我得到一个连接的加权图，权重为非负。我想将其转换为连接的非循环图，以使已删除边的权重总和最小化。输出将是删除的边缘。

我的想法：由于连接的无环图是一棵树，我可以简单地取最大n-1边，并删除所有其他边。但是，这可能并不总是正确的。它可能导致断开连接的图形。

然后，我想到了使用 dfs。我知道如何使用 dfs 检测图是否有循环，但我不知道如何检测所有涉及的边以及如何将其转换为无环图。任何帮助（代码/伪代码/算法）将不胜感激。谢谢...

我正在使用 networkx 来计算k-shortest simple paths。nx.shortest_simple_paths(G, source, target, weight=weight)按成本递增顺序返回路径列表（考虑权重的累积路径长度）。

我有兴趣获得这些路径的成本。networkX 中是否有任何简单的函数来获得这个？

这个问题类似于这个问题：Networkx 中是否已经实现了算法来返回路径长度以及路径？.

我相信该帖子中发布的答案是错误的。从如何添加自定义函数来计算图中的边权重？我做了以下解决方案（见下文）。

这是正确的方法吗？

networkx 库中有什么简单的东西吗？

我的目标是找到k-shortest path的成本。

这将输出：

概括

所以我有一个有向无环加权图，其中每条边都有一个输入和输出节点，每个节点都有一个 ID，我使用字典将所有传入边按其 ID 映射到一个节点，另一个对所有传出边执行相同操作所以当呈现节点 ID 时，我可以在 ~O(1) 时间内告诉所有传入和传出边。

要求

我需要能够添加新的随机边（即连接两个随机节点），以保证无论图形有多大，它都不会有任何循环。

我试过的

由于我完全控制了如何构建我的图，我可以对其进行拓扑排序并使用卡恩算法来确定对于两个均匀随机选择的节点 N1 和 N2，该图是否会在 O(n) 时间内产生一个循环。问题是如果它发生了怎么办？我必须尝试一个新的随机配对并重复这个过程，直到我幸运为止。这听起来好像它与图的缩放比例真的很差，因为图的边缘越密集，一个新的随机图就越有可能创建一个循环。

我还阅读了这篇文章： 生成随机 DAG ，这在本质上与我的问题相似，但是，我不能使用建议的解决方案来根据节点的 ID 连接节点，而只能连接较小的 ID（之前的节点）由于我对这个问题有其他限制，所以节点是新的）。

问题

有没有办法设计一个结构，只允许我在节点之间随机选择，如果通过新边缘连接，任何一个都不会产生与内存开销无关的循环？这应该是一个 O(1) 操作。

我想构建一个无向加权图（作为python dict），其中权重是由 Mapdata.csv 文件中给出的边连接的两个节点之间的欧几里得距离。我在谷歌上找不到任何东西。请帮我。我想要用于创建加权无向图的 python 代码。

为了在文件中表示一个图，我们列出顶点和边的数量，然后列出顶点（索引后跟它的 x 和 y 坐标），然后列出边（顶点对）。例如，下图显示了一个图形及其文件表示：

我一直在尝试从单词列表或单词字符串中构造一个问题加权图，以将单词字符串指定给命名元组列表，其中每个可能的单词组合为头和尾，附加头“根”

输入：

所需输出：

代码：

我需要输出像上面提到的那样

我一直在尝试从具有 namedtupled 数据类型的单词列表中构建最小生成树算法的问题加权图。但它不适用于 Digraphs 是我尝试过的代码

输入 = ['john', 'saw', 'mary', 'root']

所需输出：

[Arc('root',weight,'saw'),Arc('root',weight,'john'),Arc('root', weight,'mary'),Arc('saw', weight,'john '), Arc('john', weight, 'saw'), Arc('saw', weight,'mary'),Arc('john', weight,'mary'), Arc('mary', weight, 'john'),Arc('saw', weight,'mary'),Arc('mary', weight,'saw')]

我编写了一个代码来遍历无向非加权图。现在我希望这段代码适用于加权图，其中权重将确定节点之间的距离，我的代码将给出起始节点和结束节点之间的最短路径。我无法获得代码的逻辑。有人可以帮帮我吗。

问题陈述：

令G = (V,E)是一个有向图，在每条边e ∈ E上具有成本c _e ∈ ℝ 。G中没有负循环。假设有一个汇节点t ∈ V，并且对于每个节点v ∈ V，都有一个标签d _v ∈ ℝ。

给出一个算法，它在线性时间内确定对于每个v ∈ V是否为真，d _v是从v到汇节点t的最小成本路径的成本。

试图：

我发现最大的挑战是线性时间限制。这里要考虑的最相关的算法是 Bellman-Ford 算法，但运行时间为 O(|V|·|E|) 太慢，因此需要针对此问题进行修改。

我也做了一个观察：

例如，如果(u,v) ∈ E 且c _(u,v) = 1，且d _u = 3 且d _v = 5，则标签d _v是错误的。这是因为从v到u的成本为 1，从u到t的最低成本为 3，总成本为 4，比d _v给出的从v到t的假设最低成本（5 .

我不确定我是否可以使用这种洞察力来生成线性算法，但这是迄今为止我得到的最远的。

我正在处理 Java 中的编码挑战，我的驱动程序从文本文件中读取城市名称和城市之间的里程数。然后，此信息将传递给将填充加权无向图的方法。城市名称是节点，它们之间的里程是权重。我正在编写 Graph 类，并且我正在使用 Linked List 数据类型作为邻接矩阵。

在我正在使用的示例中，节点是编号的，而不是命名的，变量“origin”和“destination”是整数。有人建议我需要获取字符串的索引值并在行中使用它们：

在 addUndirectedEdge 方法中。我怎么做？我是否需要将变量“origin”和“domain”声明为整数而不是字符串？

我开始igraph结合使用 python，networkx因为前者已经实现了network community detection.

现在我只是从一个加权的、非对称的邻接矩阵和节点标签字典开始。我创建了一个有向图 G, in networkx，然后将其转换为，并用标记的节点 igraph graph, g绘制了结果。igraph

这将创建所需的图表，但我想知道最有效labelling的方法edges及其相应的权重。