问题标签 [shortest-path]

我们得到一个加权图 G 及其最短路径距离的矩阵增量。所以 delta(i,j) 表示从 i 到 j 的最短路径的权重（i 和 j 是图的两个顶点）。最初给出的 delta 包含最短路径的值。突然边缘 E 的权重从 W 减少到 W'。如何在 O(n^2) 中更新 delta(i,j)？（n = 图的顶点数）问题不在于再次计算具有最佳 O(n^3) 复杂度的所有对最短路径。问题是更新增量，因此我们不需要重新计算所有对最短路径。

更明确：我们所拥有的只是一个图和它的增量矩阵。增量矩阵仅包含最短路径的值。现在我们要根据图形的变化来更新 delta 矩阵：降低边权重。如何在 O(n^2) 中更新它？

这是我关于最大 L 总和的第一个问题，这是它的不同且困难的版本。

问题：给定一个mxn 正整数矩阵，求从第 1 行到第m 行的最小 L 和。L(4项)喜欢象棋马步

示例：M = 3x3

0 1 2

1 3 2

4 2 1

可能的 L 步是：(0 1 2 2), (0 1 3 2) (0 1 4 2) 我们应该从第 1行到第3行，总和最小

我用动态编程解决了这个问题，这是我的算法：

1.取一个mxn另一个Minimum L Moves Sum数组并复制主矩阵的第一行。我称之为（MLMS） 2.从第一个单元格开始，向上查找 L 移动并计算它
3.如果它小于存在值，则将其插入 MLMS
4.执行步骤 2. 直到第 m行
5.选择最小值在第m行求和

让我逐步解释我的示例：

1. M[ 0 ][ 0 ] sum(L1 = (0, 1, 2, 2)) = 5 ; 总和（L2 =（0,1,3,2））= 6；所以 MLMS[ 0 ][ 1 ] = 6
   sum(L3 = (0, 1, 3, 2)) = 6 ; 总和（L4 =（0,1,4,2））= 7；所以 MLMS[ 2 ][ 1 ] = 6
   

2. M[ 0 ][ 1 ]总和（L5 = (1, 0, 1, 4)) = 6; 总和（L6 =（1,3,2,4））= 10；所以 MLMS[ 2 ][ 2 ] = 6
   

   ... 最后一个 MSLS 是：
   0 1 2
   4 3 6
   6 6 6
   这意味着 6 是从 0 到 m 可以达到的最小 L 和。

我认为它是O(8*(m-1) n) = O(m n)。是否有适合此问题的最佳解决方案或动态规划算法？

谢谢，对不起，很长的问题

我想知道是否有一种算法可以通过从头节点到尾节点的图来找到最短的节点序列。该图从头节点分支出来，任意复杂，收敛于尾节点。节点之间的所有连接都是未加权的。

我正在考虑解决这个问题，从头节点和尾节点开始探索性步骤，直到图形两端的节点接触等，但我想知道在我（重新）发明之前是否存在“更好的轮子” .

如果我们去特定的顶点，我们如何使用 Dijkstra 或 Bellman-Ford 的算法来找到图中某些边会受到影响的最短路径。这样，受影响边缘的长度将大于或小于原始长度。

我正在为我的一些工作寻求一些帮助。

任务是创建一个伦敦地铁旅程规划器。

编辑：-

目前我有一个哈希表中带有边缘数据的节点的邻接列表。

我想找到一种方法来使用广度优先搜索来获得任意两个顶点之间的最短路径。

顶点按照管图的外观进行逻辑连接。每个车站的边缘都使用： (this_station, next_station, tube_line) <- 这是我对每个车站的信息。

遍历这个非常棘手。任何帮助都非常感谢！

我已经为三个班车路线制作了一个带有成本（每个车站之间的距离）的有向图。任何穿梭路线的车站到车站的票价都是一样的，因此唯一要做的就是尽量减少换乘。

我希望它以这种方式工作。我想从 Station A -> C 出发。为简单起见，我们首先假设车站之间的距离为一 (1)。

由于路线 1 和路线 2 中都有一条从 A -> C 的路径，因此我将选择成本最低的路线 2。我已经这样做了。

但是如果我想从 Station C -> Y 出发，没有从 C -> Y 的直达路线。所以我必须从 1 或 2 出发，然后在 A 下车，然后从 A -> Y。基本上，我只是希望尽量减少班车接送和行驶距离。

有没有流行的算法呢？

我正在做一个学术项目：编写一个库，用于在大型加权有向图上找到最短路径。

规格为：

• 示例数据集是一个包含 1500 个顶点的图，每个节点平均有 5.68 条边。规格可能会有所不同，最多 20.000 个节点。

• 此外，我正在一个 cpu / memory bound 环境中工作：Android。

• 边缘权重不是微不足道的，也不是恒定的。它取决于图形的可变状态。

• 我们必须离线工作。

我面临几个困难：

• 我需要一种有效的方法来存储、检索和更新图形数据。我应该使用带有来自 Java 类的查询的 SQLite 对象、堆上的大型自定义 java 对象，还是什么？我认为这是对性能最关键的方面。

• 我需要一种有效的方法来实现某种短路径算法。由于所有权重都是正数，我是否应该应用 Dijikstra 算法和 ArrayList 作为访问节点的容器？

• 这是使用 NDK 的好案例吗？该任务是 CPU 密集型的，但它也会频繁访问内存，所以我不这么认为，但我愿意做出贡献。

• 永远记住资源稀缺，内存不足，磁盘慢，cpu 是宝贵的（电池）。

欢迎任何建议，干杯:)

我需要图形工具来显示和编辑最短路径问题（或其他图论问题）的数据，所以有人知道这个工具吗？

我想使用 Djikstra 的最短路径之类的东西在 Python 中实现行驶方向。该算法要求数据以图结构表示。原始 GIS 数据（例如形状文件或OpenStreetMap 数据，但是，它们的数据表示方式不同。因此，我想知道是否有任何 Python 库可以将 GIS 数据转换为图形结构？

在 Java 中，我发现 GeoTools完全符合我的描述。Python中有没有类似的库？

我想在我的 matlab 应用程序中嵌入 google map api，以查找两个不同位置（坐标）之间的最短距离。我试图在上面显示折线..

如何在 matlab 中实现这一点？

谢谢阿比