问题标签 [weighted-graph]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
1 回答
41 浏览

java - 为什么我的 Dijkstra 算法适用于负权重?我是否错误地实现了它并且我是否牺牲了运行时间?

我可以得到一些帮助来弄清楚我的代码有什么问题吗?只要它们不处于负循环中,它就适用于正负加权边缘。我尝试调查它,但我不确定我哪里出错了。我猜我做错了什么主要只会影响时间复杂度,但我仍然可能是错的。

0 投票
1 回答
274 浏览

python-3.x - Mayavi:设置 pipeline.tube 半径

我正在使用 Mayavi 绘制一个 3D 网络,

我想改变边缘/管半径。所以我尝试了

我收到一条错误消息,

从错误中,我了解到无法将列表分配给 tube_radius。在这种情况下,我不确定如何为每条边分配不同的半径。

有关如何分配边缘权重/边缘半径的任何建议都会有所帮助。

编辑:完整的工作示例

要在预期输出中添加的新边权重:

0 投票
1 回答
5789 浏览

python - 如何使用 Networkx 创建每个节点至少有 1 条边的随机图

我已经设法创建了一个随机无向加权图,用于使用 Dijkstra 算法进行测试,但我怎样才能做到这一点,以便每个节点至少有一个将它们连接到图的边?

我正在使用 Networkx,我的图形生成器如下:

这很好地创建了图表,并且我设法绘制了它,所以我实际上可以看到它,我的问题是边缘创建的概率。我不希望它太高以至于所有节点都具有最大数量的边,但是设置低值可能会导致节点的边数为 0。有没有办法确保每个节点至少有一条边?

0 投票
1 回答
739 浏览

c++ - 使用 Dijkstra 算法跟踪两个节点之间的最短路径

我对 c++ 很陌生,并且一直无法修改 Dijkstra 的算法来跟踪两个节点之间的最短路径,而不仅仅是最短距离。我让它正确计算最短距离。这是计算最短距离的函数:

这是我用来测试的图表:

有人可以帮我最短路径吗?

0 投票
1 回答
30 浏览

python-3.x - 在 Python 3 中实现呼吸优先搜索(如何将 'Set' 转换为 'Dictionary'

大家好,我开始学习 Python。我使用字典图的呼吸优先搜索方式是错误的。我有一个错误,我的代码是

我在这里尝试过。

0 投票
1 回答
1258 浏览

python - python中映射系统的加权无向图

我想知道如何在 python 中为 map 实现加权无向图。地图上有城市和一些道路,它们连接城市并具有各自的权重。

0 投票
1 回答
2451 浏览

python - 如何有效地从networkx图中获取边权重?(nx.Graph)

我试图从 a 中获取边缘权重,nx.Graph但我能找出的唯一方法是遍历整个网络。networkx假设我nx.Graph以前没有,有没有更有效的方法来做到这一点pd.DataFrame?这是为了networkx ≥ 2.0.

0 投票
0 回答
111 浏览

matlab - 图的权重作为matlab图中线的长度

我正在尝试在 matlab 中构建一种图:对于每个顶点,我知道它的邻居(因此,我有边列表),以及顶点邻居之间的距离。该距离被保存为边缘的权重。因此,权重实际上是节点之间的物理距离。

目前我只能将更宽的线与更大的权重相关联,但这还不够。

我实际上希望将更长的线与更大的权重相关联,这样我就可以从我的数据中直观地构建合适的几何图形。

有小费吗?

编辑:距离使得绘图是可能的。

在此处输入图像描述

0 投票
1 回答
119 浏览

algorithm - 具有所需顶点的有向加权图

给定:一个有向加权图 G=(V, E),一些顶点是红色的,一些是蓝色的,其余的是白色的,权重 Ti 是允许从任何顶点红色顶点到任何蓝色顶点的最大权重。

问题:创建一个算法,找到从源节点 S 到权重最小的目标节点 T 的路径,并且在到达顶点 T 之前,该路径从红色顶点到蓝色顶点的最大权重为 Ti。算法应该有时间复杂度 O(n^3)

评论:我不知道如何开始,我认为这是 Dijkstra 算法的一些变体,我看到有些人在谈论制作图表的副本并连接副本,但除此之外,我不确定是什么这个算法的设置看起来像。任何帮助,将不胜感激。

0 投票
0 回答
33 浏览

python - 如何找到加权无向图中所有节点的总和

我想找到这个图的所有不重复的 d 值的总和作为一个例子,(a2 a3)和(a3 a2)被认为是一次

这是我使用的方法

这是目前我得到总和的输出,那么有什么更容易做的事情来获得唯一键的总和吗?

预期输出是唯一值的总和(例如,考虑 'a1,a3': 2 和 'a3,a2': 1)一次