问题标签 [shortest-path]

正如标题所说，我正在尝试实现一种算法，找出给定图中所有节点对之间的距离。但还有更多：（可能对您有帮助的事情）

• 该图未加权。这意味着所有边缘都可以被认为具有权重 1。
• |E| <= 4*|V|
• 该图非常大（最多〜144深度）
• 图是有向的
• 可能有循环
• 我正在用python编写我的代码（如果你引用算法，代码也会很好:)）

我知道所有对的 Johnson 算法、Floyd-Warshal和Dijkstra。但是当图有权重时，这些算法很好。

我想知道是否有更好的算法适合我的情况，因为这些算法适用于加权图。

谢谢！

我想用 NetworkX 库实现最短路径算法。就我而言，我的权重函数从其他边缘属性中得出值。因为重量是一个计算值，我不想将它存储为一个额外的属性以避免复杂性，例如在其他属性更改时更新值。然而，NetworkX 的算法 API似乎需要权重作为边缘数据密钥。

所以我想知道是否可以不存储价值？我的理想情况是为算法指定一个自定义权重函数。

现在我想做的是，对于从 V1 到 V2 的每条边，我想设置 V2 到 V1 的距离（D）。如果 D 小于 V2 的当前距离，那么我们希望将 V2 的当前距离设置为 D，并将 V2 的前任设置为 V1。

我已将 V1 声明并初始化为最短距离（这只是初始点），并将其标记为完成。

问题：如何声明 V2 并设置它的距离？

我必须在不使用斐波那契堆的情况下实现 Dijkstra 和 Sedgewick-Vitter 算法。有关 Dijkstra 完整互联网的信息，但我找不到 Sedgewick-Vitter 算法的伪代码或示例。我只发现 McHugh, Algorithmic Graph Theory book 中有一些信息，但我找不到免费的 pdf。所以也许有人知道这个算法并且可以分享信息、伪代码、链接？

干杯!

在我的应用程序中，假设用户选择了 4 个城市来访问，其中 S 作为起始城市，D 作为目的地城市，那么是否有任何 API 或 web 服务。

这里用户只访问一次城市，输出应该是覆盖所有城市的 A 和 D 之间的最短路径。如果有人有任何其他想法，也欢迎。

感谢和问候姆鲁根

[底部更新（包括解决方案源代码）]

我有一个计算机可以帮助解决的具有挑战性的业务问题。

沿着山区流淌着一条蜿蜒曲折的长河，水流强劲。沿着河流的某些部分，有一片对环境敏感的土地，适合种植一种特殊类型的稀有水果，这种水果的需求量非常大。一旦田间劳动者收获水果，时钟就开始滴答作响，将水果送到加工厂。尝试将水果运送到上游或陆上或空中是非常昂贵的。到目前为止，将它们运送到工厂的最具成本效益的机制是在下游的容器中，该容器仅由河流的恒流供电。我们有能力建造 10 个加工厂，需要将这些加工厂设在河边，以尽量减少水果在运输过程中的总时间。然而，这些水果可能需要很长时间才能到达最近的下游工厂，但那段时间直接损害了它们的销售价格。实际上，我们希望最小化到最近的相应下游工厂的距离总和。植物可以位于水果接入点下游低至 0 米处。

问题是：为了利润最大化，如果我们找到了 32 个水果种植区，那么 10 个加工厂应该在河流上游多远，这些区域到河底上游的距离（米）：10 , 40, 90, 160, 250, 360, 490, ... (n^2)*10 ... 9000, 9610, 10320？

[希望所有致力于解决这个问题以及创建类似问题和使用场景的工作都可以帮助提高人们对软件/商业方法专利的破坏性和扼杀性质的认识并产生普遍的抵制（无论这些专利在多大程度上被相信在当地是合法的）。]

更新

更新1：忘了补充：我相信这个问题是这个问题的一个特例。

更新2：我写的一个算法在几分之一秒内给出了答案，我相信它相当好（但它在样本值上还不稳定）。稍后我会提供更多细节，但简短如下。将植物以相等的间距放置。循环遍历所有内部植物，在每个植物上，您通过测试其两个邻居之间的每个位置来重新计算其位置，直到在该空间内解决问题（贪心算法）。因此，您优化工厂 2，保持 1 和 3 固定。然后工厂 3 保持 2 和 4 固定......当你到达终点时，你循环回来并重复，直到你进入一个完整的循环，每个加工厂的重新计算位置停止变化。同样在每个循环结束时，你尝试移动紧挨着拥挤的加工厂，而且都在彼此附近 水果堆到远处有水果堆的地区。有很多方法可以改变细节，从而产生准确的答案。我有其他候选算法，但都有故障。[我稍后会发布代码。] 就像下面提到的 Mike Dunlavey 一样，我们可能只想要“足够好”。

给出一个可能是“足够好”的结果的想法：

更新 3：mhum 首先给出了正确的精确解，但（还）没有发布程序或算法，所以我写了一个产生相同值的程序或算法。

如果我添加或删除一条比计算前后距离更快然后减去的单条边，有什么方法可以找出图形的平均测地线距离会改变多少？

我正在对其状态由无向图表示的系统进行 Metropolis Monte Carlo 模拟。系统的能量取决于该图的平均测地距离。

在每一个蒙特卡洛步骤，我必须提议对图表进行修改，然后计算由于该修改引起的能量变化。我只是选择一个随机边缘并翻转它（如果边缘不存在，则添加边缘，如果存在则移除边缘）。我现在做的是一种蛮力：

我宁愿这样做：

如果计算能量差异比计算能量本身快得多。如果给定边缘以更快的方式翻转（big-O-wise），如果有一种方法可以计算平均测地线长度的差异，这是可能的。

有没有办法做到这一点？我知道很难预测一条边的变化会影响哪些路径，但是……也许我很幸运！:D

编辑：我不在乎我必须为你想到的任何算法使用什么表示。如果它节省了我的时间，我愿意这样做。

我的图通常有点小（顶点数通常少于一百，边数在少数和完全连接之间变化）。问题是我必须重复这个循环很多很多步骤以达到平衡，并且他们为很多很多不同的条件中的每一个计算许多可观察的...... :(

编辑 2：我不需要单独的测地线路径或其长度，只需要平均测地线长度。

问候溢出者，

我有一个加权有向图，我想要覆盖所有节点的最低成本树，其中根是图的特定给定节点。我不知道我是否也可以在每个节点上设置不同的最大分支，其中从该节点到其他节点（向外边缘）的分支数等于或小于该最大值？

那么最适合我开始阅读需求的算法是什么？我希望它足够快:)

非常感谢 ！

考虑接下来要做的事情

您需要做什么（在运营中）：

myPoints 有一组点，我考虑myPoints[initialindex]我的 StartPosition。并且返回的数组是为了得到最短路径而排序的点。

我似乎不知道如何申请 Floyd–Warshall niether Dijkstra 是否适用。

对不起，文字墙，它尽可能简洁！

我有一个非常大的有向图 G 和 G 内的顶点子集 S p 和 G 中的一个顶点 q，即在诱导子图中这两个顶点之间存在一条边。这是关键；它比通常的诱导子图问题更复杂（我认为）。

我能想到的解决问题的最基本方法如下（我意识到它可能不是最有效的，如果您有其他不太复杂的建议，请告诉我）： 对于 S 中的每一对顶点，在 G 中测试它们之间是否存在路径。如果存在这样的路径，则在诱导子图中插入 p 和 q 之间的边。就我的目的而言，n^2 次还不错。

所以，我想我有两个问题：1）确定两个顶点之间是否存在路径的最快方法是什么？我不需要知道路径，只需要知道它是否存在。此外，如果我可以对整个图形进行一些预处理以加快计算速度，那可能是什么，因为我必须在每对顶点之间执行此计算？

2）有没有比我建议的更快的方法来找到我描述的诱导子图的类型？

非常感谢你的帮忙！