问题标签 [shortest-path]

这就是问题：

我有 n 个点 (p1, p2, p3, .. pn)，每个点都可以以确定的成本 x 连接到任何其他点。

每个点都属于一组点类型中的一个（例如“A”“B”“C”“D”......）。

该方法的输入是我要遵循的路径，例如“ABCADB”。

输出是连接我在输入中给出的类型的点的最短路径，例如“p1-p4-p32-p83-p43-p12”，其中 p1 是 A 型，p4 是 B 型，p32 是 C-型，p83 为 A 型，p43 为 D 型，p12 为 B 型。

“简单”的解决方案包括计算所有可能的路径，但计算成本非常高！

有人能找到更好的算法吗？

正如我在标题中所说，我不知道它是否存在！

更新：

阻止我使用 Dijkstra 和其他类似算法的关键是我必须根据类型链接这些点。

作为输入，我有一个类型数组，我必须按该顺序链接。

这是 Kent Fredric 的图片（非常感谢），它描述了初始情况（红色允许链接）！

一个真实的例子：

一个人早上想去教堂，下午去餐馆，最后去博物馆。

地图上有 6 座教堂、30 间餐厅和 4 座博物馆。

他希望教堂-休息-博物馆的距离尽可能小。

我正在寻求一些以视觉方式展示 Floyd-Warshall 有用性的想法。到目前为止，我能想到的只是生成一个随机图，允许用户选择开始/结束并突出显示最短路径。有哪些更有趣但更简单的寻路有用性演示？

我有一个带有 s 和 t 顶点的图，我需要找到它之间的最短路径。该图有很多我想利用的特殊属性：

• 该图是一个 DAG（有向无环图）。
• 我可以在 O(|V|) 时间内创建拓扑排序，比传统的 O(|V + E|) 更快。
• 在拓扑排序中，s 是列表中的第一项，t 是最后一项。

有人告诉我，一旦我对顶点进行了拓扑排序，我就可以比我目前的 Dijkstra 统一成本标准更快地找到最短路径，但我似乎找不到它的算法。

伪代码将不胜感激。

编辑：从 s 到 t 的所有路径都具有相同数量的边。边有权重。我正在寻找成本最低的路径。

对于数据结构项目，我必须找到两个单词（如"cat"和"dog"）之间的最短路径，一次只更改一个字母。我们得到了一个拼字游戏单词列表，用于寻找我们的路径。例如：

我已经使用广度优先搜索解决了这个问题，但正在寻找更好的东西（我用特里树表示字典）。

请给我一些想法，以获得更有效的方法（在速度和内存方面）。一些荒谬和/或具有挑战性的东西是首选。

我问了我的一个朋友（他是一名大三学生），他说这个问题没有有效的解决方案。他说我会在学习算法课程时了解原因。对此有何评论？

我们必须逐字逐句。我们不能去cat -> dat -> dag -> dog。我们还必须打印出遍历。

我正在尝试构建一种方法，该方法在未加权图中返回从一个节点到另一个节点的最短路径。我考虑过使用 Dijkstra 的，但这似乎有点矫枉过正，因为我只想要一对。相反，我实现了广度优先搜索，但问题是我的返回列表包含一些我不想要的节点 - 我如何修改我的代码以实现我的目标？

我需要在图中找到添加节点最少的最短路径。开始和结束节点并不重要。如果图中指定的 n 节点之间没有路径，我可以添加一些节点来完成最短树，但我想添加尽可能少的新节点。

我可以使用什么算法来解决这个问题？

我有一个互连边列表 ( E)，如何找到从一个顶点连接到另一个顶点的最短路径？

我正在考虑使用最低共同祖先，但边缘没有明确定义的根，所以我认为该解决方案行不通。

最短路径由遍历的最小顶点数定义。

注意：可能存在连接两个顶点的多路径，因此显然广度优先搜索不起作用

我想解决以下问题：

我有一个 DAG，其中包含需要完成的城市和工作。这些工作适用于可以装载定义限制的卡车。卡车装载的越多，旅行就越好。有些工作是为了加载一些东西，有些是为了加载定义的东西。即使他们之间没有工作要做，您也可以随时从城市 a 开车到 b。最后一个限制是我总是需要从 a 城市开始并返回 a，因为那里有卡车的家 :)

我首先想到的是 Dijkstra 的最短路径算法。我可以轻松地将其转换为最长路径计算。我现在想到的问题是，所有这些算法都用于计算从顶点 a 到 b 的最短或最长路径，但我需要它从 a 返回到 a - 在一个圆圈中。

有没有一些让我心动的？

感谢您的反馈意见！

马可

我正在寻找一种方法来证明 bicriteria 最短路径问题是 np 完备的。也就是说，给定一个具有长度和权重的图，我需要知道图中是否存在从 s 到 t 的总长度 <= L 且重量 <= W 的路径。

我知道我必须解决一个 NP 完全问题并将其简化为这个问题。我们有以下问题可供选择：3-SAT、独立集、顶点覆盖、汉密尔顿循环和 3 维匹配。

任何可能可行的想法？

谢谢

“Floyd-Warshall 算法”和“Dijkstra 算法”有什么区别，哪个最适合在图中找到最短路径？

我需要计算网络中所有对之间的最短路径并将结果保存到数组中，如下所示：