求有色图中的最短路径
我试图解决的问题是：
给出一个图，其中每个边都用红色或蓝色着色：
a）给出了生成两顶点(s，t)之间经过最小数量红边的路径的算法。
共有1个答案
关于您的算法，有两个重要细节需要记住：
-
在您的场景中，
- 节点可以多次添加到队列中。不过，你只能探索一次。您可以通过为每个节点维护一个布尔标志来实现这一点，该标志告诉您是否已经探索了一个节点。
- 只能在将
t从队列中取出后立即停止算法，而不能在将其放入后立即停止算法。
如果你这样做（你的问题并没有表明你不这样做），你的算法确实是正确的。
修改后的BFS实际上使用双端队列作为2值优先级队列来实现Dijkstra算法：如果q是您的队列，那么就有一个索引i，这样q[1..i]只包含距离m的节点，q[i+1..]只包含距离m+1的节点。
我如何将其扩展到答案b）？
您可以通过维护一个4值优先级队列（例如，实现为两个双端队列）来扩展这个概念。一个队列将保存距离M红边的节点，另一个队列将保存距离M+1红边的节点。两者都是通过增加蓝边的数量来排序的（每个蓝边中也只有两个不同的距离值）。
-
在一个加权有向图中，我需要找到两个结点s，t之间的最短路径。以下是限制： 权重可以为负值。 路径必须经过一个特定的边，让我们从节点u到V调用her e和shes。 输出路径必须简单，即我们只通过一个节点一次。 因为我希望它最短，所以我将检查在从s到u之前从v到t运行bellman ford是否比相反的方式更快（如果有节点，两个节点都使用where是放置它的最佳位置）。 谢谢你的帮助！
-
给出了一个边上具有任意权的有向无环图和两个特定结点s和t，其中s的内度和t的外度为0。如何确定成本为正的s到t的最短路径？
-
我有一个有向加权图
-
我需要帮助在一个未加权无向图中找到两个节点之间的所有最短路径。 我能够使用BFS找到一条最短路径，但到目前为止，我还不知道如何找到并打印出所有路径。 知道我可以使用的算法/伪代码吗？
-
我确实有一个图(~250个节点）。要连接到一个节点，我必须用points->加权图购买它。有些节点总是被占用（“声明的节点”），我可以从这些节点开始连接到其他节点。此外，我的点数有限。所有节点都可以连接在一起。 有什么方法可以得到一个图，其中所有的节点都必须连接在一起，点最少？如果可能的话，以给定的最大点数。 第二）有没有一种方法可以使它不需要一个完全连通的图？例如：一个“必须有节点”的节点直接连