问题标签 [weighted-graph]

我想计算从源 S 到汇 T 的最短路径。
但是该路径必须从节点 1 到节点 2 至少传递一次。

例如：S->...->node1->....->node2->....->T

而且我只需要运行一次最短路径算法（意思是，我不允许在三个不同的最短路径调用中计算从 s 到 node1 的路径，然后是 node1 到 node2 和最后 node2 到 T 的路径）

我首先想到的是 TSP，因为在 TSP 中，每个节点都“必须”通过。但是TSP的复杂度太高了。

我是否可以修改 TSP 以将其复杂性降低为多项式，或者您是否有其他方法来解决这个问题

我在 R 中使用 igraph 和 statnet 创建了一个加权网络。我现在正在使用 statnet 研究我的加权网络的中心性度量，但是我获得的中心性度量好像 statnet 没有考虑我的边值。这是一个使用度中心性度量来说明我的问题的小例子。

我使用 igraph 创建了我的网络：

然后我需要使用 statnet 包，所以我按照以下方式对其进行了转换

然后我想计算度中心性，首先不考虑边缘值（degree_unweighted），然后考虑边缘值（degree_weighted）

但我最终得到了完全相同的中心性度量。我不知道为什么 statnet 在我指定ignore.eval=FALSE. 我对其他中心性度量（介数、接近性、特征向量）也有同样的问题。

所以我想找到这张图上任意两个节点之间的最短距离，我知道实现这个想法所需的算法，但我不确定我将如何去做。我将邻接列表创建为一个 ArrayList，其中包含一个 startValue、EndValue 和一个权重。例如： Banstead 是节点 1，它被创建为一个对象： CreateNode(1,2,4) 所以从 Banstead 到 Coulsdon 的成本是节点 1 和节点 2 之间的 4。

这是代码

}

输出只是邻接列表的显示：

... 等等。

我如何实现一种算法来找到任意两个随机节点之间的最短路径，比如 Banstead 和 Horley。谢谢。

我有一个带有非负加权边的有向图，其中两个顶点之间有多个边。

我需要计算所有对的最短路径。该图非常大（2000 万个顶点和 1 亿条边）。Floyd-Warshall 是最好的算法吗？有没有很好的库或工具来完成这个任务？

给定一个图，其顶点为城市，边为城市之间的距离。每个城市都有一定数量的与之相关的假期。最初，您将获得起点。现在的目标是在图中找到一条路径，以便我们需要收集尽可能多的假期，同时最小化距离。

例如：考虑一个图：顶点权重： (City -> Holidays) A -> 30 B -> 35 C -> 45

边权重 A -> B (Distance is 2) A -> C (Distance is 8)

如果我们从 A 开始，我们可以收集的最大假期是 65，通过路径 A -> B，距离为“2”。我们不选择路径 A -> C，即使它给出的假期为 75，因为距离是“8”

我对图表仍然很陌生，并且正在为一个学校项目构建一个加权有向图。我能够完成所有功能，除了找到从一个节点到另一个节点的最小加权路径的功能。我能够找到一条路径，但不知道如何存储所有路径然后获得最小加权路径。我的图表由一个向量表示。

我创建了一个辅助函数，它为我提供了一条从源到目的地的路径，以及一个找到路径权重的函数。它们都可以工作，但我无法找到找到所有路径的路径而不是找到的第一个路径。

此代码返回从“from”到“to”的“a”路径列表。相反，我希望它返回重量最小的那个。我必须使用已设置的函数 getPathWeight(const list& path) 来查找每条路径的权重并进行比较，但是我怎样才能将所有路径放在一个地方？

更新最低限度的工作示例，包括：

主文件

WeightedDiagraph.cpp：

加权图.h：

我正在尝试编写蛮力算法来找到从 s 到 t 的最短路径。该图是加权的，也有负加权边。无需考虑负循环。基本上退出，如果有的话。

我编写了 Bellman-Ford 算法来解决这个问题。它工作得很好。（以防“使用更好的算法”评论）但是，作为第二步，我需要实现蛮力算法。我试图把它写在广度优先搜索算法上，但是正如我提到的，有负面的边缘。因此，在某些情况下，我需要重新访问一些节点。蛮力算法。对于具有非负边的图：

如何根据边缘权重对 igraph 中边缘不太厚的加权网络图进行标准化？

我想使用 Stata 为两个连续变量绘制一个置信椭圆（有时也称为浓度椭圆）。

有一个社区贡献的命令ellip需要这种图，其作者 Anders Alexandersson 在Stata Journal上提供了详细描述。但是，我想为椭圆应用权重，这是使用此命令无法实现的。

下面是一个可重复的示例，我尝试1000使用人口规模作为权重来绘制每个居民的婚姻数量与美国各州城市人口的百分比：

结果如下所示：

如您所见，散点图的点按人口规模加权/膨胀的第二个椭圆应该可能移到右下角。

如何在 Stata 中创建加权置信椭圆？

我创建了一些代码来计算加权全局效率，但是，代码运行时间太长。我需要使代码更高效，或者我需要找到一种更有效的方法来计算大型数据集（最多 6000 个点）。

我已经对代码进行了很多编辑，并且尝试了 igraph（没有用于加权全局效率的函数），但没有什么能让我完成计算的速度足够快。我当前的代码都显示在下面

结果在计算加权全局效率时是准确的，但是花费的时间太长。