如何在线性时间内找到边权为0或1的有向图中的最短路径？
本文对BFS法在无权有向图中寻找单源最短路径的方法进行了改进，并在O(n+m)时间内解决了上述问题。其中N是顶点数，M是边数
我曾想过以下几点：
将边缘权重更改为1和2。然后在长度为2的路径中创建虚拟顶点以将这些边转换为权重为1的边。但这会给出错误的答案。
在更一般的情况下，当边权值在线性时间内介于0和MAX之间时，如何在有向图中找到单源最短路径。（MAX为最大边缘权重）
共有1个答案
您可以对bfs进行一些修改：维护一个deque而不是队列，如果使用0边，则在deque的前面添加一个顶点，否则在deque的后面添加一个顶点。（我现在的意思是0-1的情况）
-
在一个加权有向图中，我需要找到两个结点s，t之间的最短路径。以下是限制： 权重可以为负值。 路径必须经过一个特定的边，让我们从节点u到V调用her e和shes。 输出路径必须简单，即我们只通过一个节点一次。 因为我希望它最短，所以我将检查在从s到u之前从v到t运行bellman ford是否比相反的方式更快（如果有节点，两个节点都使用where是放置它的最佳位置）。 谢谢你的帮助！
-
给出了一个图G=(V，E)，它是正加权的，有向的，无圈的。我设计了一个在O(k(m+n))中运行的算法，用于报告从s到T的k-边最短路径。k-边最短路径定义为从s到t的具有k条边的路径，并且对于从s到t的所有路径，该路径的总权也必须是最小的。 由于BFS不能单独用于寻找最短路径（除非权重相等），我认为运行时间意味着使用BFS寻找具有k条边的路径。让我感到困惑的是k，因为我认为它意味着表演BFS k
-
给定一些无向边加权图，什么算法可以用来找到从某个顶点v到另一个顶点w的最短路径？ 对于有向边加权图，可以使用Dijkstra的最短路径算法，但我使用的是无向图，所以它不起作用。 对于非边加权的图，可以使用广度优先搜索（BFS），但我使用的是边加权图，所以它不起作用。 既然它是无向和边加权的，一般最短路径法是什么？
-
我有一个一般性的问题，关于如何在边没有权的无向图中找到最短路径和最长路径。 我们需要使用DFS算法来寻找图中的最长路径，而我们需要使用BFS算法来寻找图中的最短路径，这是一个正确的结论吗？
-
我有一个有向加权图
-
问题内容： 我需要一种算法来找到地图上两点之间的最短路径，其中道路距离用数字表示。 提供的内容：开始城市A目的地城市Z 城市之间的距离清单： A-B：10 F-K：23 R-M：8 K-O：40 Z-P：18 J-K：25 D-B：11 M-A：8 P-R：15 我以为我可以使用Dijkstra的算法，但是它找到所有目的地的最短距离。不只是一个 任何建议表示赞赏。 问题答案： 就像Splinter