如何在知道所有图节点和权重的情况下获取我们当前 "on" 图的路径？
How to obtain a path we are currently "on" the graph while knowing all graph nodes and weights?
我有一个由节点和边的权重组成的网络。我认识他们所有人。我得到一个 "packet"，我知道它正在从 A 到 B 当前在节点 C 上移动。如何获得当前可以遍历的最小路径（下一个和前一个节点）？
更新：
尽管接受的答案中的声明我的会起作用。因为
如果从A到B只有一条最短路径，那么C就是最短的小路。接受的答案本身用以下短语明确声明：
The shortest path A -> C -> B must have the shortest A->C and C->B subpaths.
和
It is trivial to prove.
- 所以
C 不在最短路径上的唯一可能性是如果有多个。接受的答案根本 没有解决这个问题。所以它会给出如果没有错误但可能具有误导性的结果。虽然这里明确指出
you need to find all shortest paths
- 哪种方法最简单或最快完全是另一回事。因为性能将取决于特定算法的具体实现和网络拓扑。找到一条长路径不一定比找到两条小路径慢（没有缓存......缓存会增加复杂性）。
- 无论如何，检查有几条最短路径的事实是更通用的方法，因为它允许对用于计算数据包路径的算法的实现进行预测。
- 而且，如果@PakUula 表示 三点之间的最短路径
A->C->B 不一定与 [=64] 之间的最短路径相同=]两分 A->B 那么他的回答是不正确的。正是因为路径 A->C->B 不是两点之间的最短路径，所以 C 没有经过最短路径，所以我们不知道用于构造数据包路径的算法 and/or 我们对网重的认识是错误的。在那种情况下，请参阅 theoretical exercise 和此答案的结尾。
答案本身：
我想我们假设数据包总是试图遵循最短路径。
作为一个数据包，在它开始从 A 到 B 的旅程之前，需要知道如何让它首先移动它已经需要知道最短路径。所以你只要找到A和B之间的这条最短路径，然后你就可以找到它上面的C节点在哪里。
可以找到最短路径，例如，Dijkstra 算法或其他算法。您可以通过类似 "graph shortest path".
的请求在互联网上找到它们
正如您所说，边的权重是已知的。然后就没有别的了。 C 节点将始终位于最短路径上。 因为只有一条最短路径... 实际上 - 没有。相同权重的路径可以有多条
所以你的任务有点不同——你需要找到所有条最短路径s。然后你需要找到哪个 then include C 节点。同样，节点 C 可以有多个路径。所以在这些情况下你不能 100% 肯定地回答你的问题。
作为理论练习：如果在 任何 条最短路径上没有 C 节点怎么办？这意味着可能有一些 "obstacles" 在路上，计划必须改变。
那么可以做些什么呢？
找到下一个节点非常容易：只需找到 C 和 B 之间的最短路径即可。但答案并不总是确定的，因为可能有几条相同重量的路线。
但是在没有关于 "obstacles" 的信息的情况下，不可能 找到前一个节点。因为取决于它们，数据包可以来自 任何 方向。这实质上意味着图表的权重已经改变，而你不知道它们。
最短路径 A -> C -> B 必须具有最短的 A->C 和 C->B 子路径。证明是微不足道的。 注。最短路径 A -> B 可能不会遍历 C。因此，如果您没有从最短路径中正确选择 C 的先验保证，@x00 的回答可能会失败。
前一个节点是路径 A->C 的最后一段，下一个节点是路径 C->B 的第一段。
可以使用 Dijkstra 算法计算最短路径。
我有一个由节点和边的权重组成的网络。我认识他们所有人。我得到一个 "packet"，我知道它正在从 A 到 B 当前在节点 C 上移动。如何获得当前可以遍历的最小路径（下一个和前一个节点）？
更新：
尽管接受的答案中的声明我的会起作用。因为
如果从
A到B只有一条最短路径，那么C就是最短的小路。接受的答案本身用以下短语明确声明：The shortest path
A -> C -> Bmust have the shortestA->CandC->Bsubpaths.和
It is trivial to prove.
- 所以
C不在最短路径上的唯一可能性是如果有多个。接受的答案根本 没有解决这个问题。所以它会给出如果没有错误但可能具有误导性的结果。虽然这里明确指出you need to find all shortest paths
- 哪种方法最简单或最快完全是另一回事。因为性能将取决于特定算法的具体实现和网络拓扑。找到一条长路径不一定比找到两条小路径慢（没有缓存......缓存会增加复杂性）。
- 无论如何，检查有几条最短路径的事实是更通用的方法，因为它允许对用于计算数据包路径的算法的实现进行预测。
- 而且，如果@PakUula 表示 三点之间的最短路径
A->C->B不一定与 [=64] 之间的最短路径相同=]两分A->B那么他的回答是不正确的。正是因为路径A->C->B不是两点之间的最短路径，所以C没有经过最短路径，所以我们不知道用于构造数据包路径的算法 and/or 我们对网重的认识是错误的。在那种情况下，请参阅theoretical exercise和此答案的结尾。
答案本身：
我想我们假设数据包总是试图遵循最短路径。
作为一个数据包，在它开始从 A 到 B 的旅程之前，需要知道如何让它首先移动它已经需要知道最短路径。所以你只要找到A和B之间的这条最短路径，然后你就可以找到它上面的C节点在哪里。
可以找到最短路径，例如，Dijkstra 算法或其他算法。您可以通过类似 "graph shortest path".
的请求在互联网上找到它们正如您所说，边的权重是已知的。然后就没有别的了。 C 节点将始终位于最短路径上。 因为只有一条最短路径... 实际上 - 没有。相同权重的路径可以有多条
所以你的任务有点不同——你需要找到所有条最短路径s。然后你需要找到哪个 then include C 节点。同样，节点 C 可以有多个路径。所以在这些情况下你不能 100% 肯定地回答你的问题。
作为理论练习：如果在 任何 条最短路径上没有 C 节点怎么办？这意味着可能有一些 "obstacles" 在路上，计划必须改变。
那么可以做些什么呢？
找到下一个节点非常容易：只需找到 C 和 B 之间的最短路径即可。但答案并不总是确定的，因为可能有几条相同重量的路线。
但是在没有关于 "obstacles" 的信息的情况下，不可能 找到前一个节点。因为取决于它们，数据包可以来自 任何 方向。这实质上意味着图表的权重已经改变，而你不知道它们。
最短路径 A -> C -> B 必须具有最短的 A->C 和 C->B 子路径。证明是微不足道的。 注。最短路径 A -> B 可能不会遍历 C。因此，如果您没有从最短路径中正确选择 C 的先验保证，@x00 的回答可能会失败。
前一个节点是路径 A->C 的最后一段，下一个节点是路径 C->B 的第一段。
可以使用 Dijkstra 算法计算最短路径。