求加权图中的最短路径
给出了一个城市和航空和公路成本的图表，作为每对城市之间的边缘权重。我们得找到敏。考虑到我最多只能通过航空公司旅行一次的限制，从来源城市到目的地城市的旅行费用。
到目前为止，我的方法是：选择每条航线边一次，然后将dijkstra应用到剩下的图中，只在航线边上。有什么办法可以改善这一点吗？
共有1个答案
构造有向图(G，E)，如下所示：
设X为源城市，Y为目标城市。
对于每个城市C，而不是X，构造两个顶点:(C，yes)和(C，no)，其中“yes”表示“飞机已使用”，“no”表示“飞机未使用”。对于源城市X，只构造一个顶点(X,no)。
边缘如下：
- 从任何
(C，yes)到任何(D，no)都没有边。 - 存在从
(C，yes)到(D，yes)(resp.(C，no)到(D，no))的边，当且仅当C和D之间存在道路，且此边的权重为道路的权重。 - 从
(C，no)到(D，yes)存在边，当且仅当C和D之间存在气道，且此边的权重为气道的权重。
现在，只需在图G中找到从(X,no)到(Y,yes)(rep.to(Y,no))的最短路径，这是使用一个气道（即不使用气道）的最小成本。这两个中的最小值将是最终的答案。
其复杂性将是有向图(G，E)的最短路径问题的复杂性，该有向图的顶点数和边数（直到大O常数）与原图相同。
根据这个wiki页面，这个问题可以在O(e+vloglogv)时间内解决。为了简单起见，您当然可以使用Dijkstra。
-
在一个加权有向图中，我需要找到两个结点s，t之间的最短路径。以下是限制： 权重可以为负值。 路径必须经过一个特定的边，让我们从节点u到V调用her e和shes。 输出路径必须简单，即我们只通过一个节点一次。 因为我希望它最短，所以我将检查在从s到u之前从v到t运行bellman ford是否比相反的方式更快（如果有节点，两个节点都使用where是放置它的最佳位置）。 谢谢你的帮助！
-
我试图解决的问题是： 给出一个图，其中每个边都用红色或蓝色着色： a）给出了生成两顶点(s，t)之间经过最小数量红边的路径的算法。
-
我有一个有向加权图
-
以下是消费税： 在某些图的问题中，顶点可以有权代替边的权或增加边的权。设Cv是顶点v的代价，C(x，y)是边(x，y)的代价。该问题涉及到在图G中寻找顶点a和顶点b之间的最便宜路径，路径的代价是该路径上遇到的边和顶点的代价之和。 (a)假设图中每条边的权重为零（而非边的代价为∞)，假设所有顶点1≤V≤n（即所有顶点的代价相同），Cv=1。给出一个求从a到b最便宜路径的高效算法及其时间复杂度。 (b
-
给出了一个图G=(V，E)，它是正加权的，有向的，无圈的。我设计了一个在O(k(m+n))中运行的算法，用于报告从s到T的k-边最短路径。k-边最短路径定义为从s到t的具有k条边的路径，并且对于从s到t的所有路径，该路径的总权也必须是最小的。 由于BFS不能单独用于寻找最短路径（除非权重相等），我认为运行时间意味着使用BFS寻找具有k条边的路径。让我感到困惑的是k，因为我认为它意味着表演BFS k
-
在无向赋权图中寻找两个顶点之间的最短路径。还已知权重是小于log（logV）的整数，其中V是顶点的数量。使用贝尔曼-福特或Dijkstra算法很容易解决，但是有没有什么算法可以更快地解决呢？ 到目前为止，我一直在考虑使用BFS，将权重大于1的边划分成两个权重为1的边，但如果V是大数，就不是一个好主意。不，这不是我的家庭作业，我只是在想。
-
给我一个图中名为“a”的顶点，对于v中的每一个v，我需要找到从a到v的路径的权重，它在时间O(v+E)中权重最低。我不得不只使用BFS或DFS（尽管这很可能是BFS的问题）。 我想过要制作一个新的图，其中边为0的顶点是统一的，然后在它上面运行BFS，但是这会破坏图的方向（如果图是无向的或者权重是{2,1}，对于边为2，我会创建一个新的顶点）。 如果有任何帮助，我将不胜感激。 谢谢
-
我试图用BFS找到无向加权图的单源最短路径算法。 我想出了一个解决方案，将每个边权重转换成顶点之间的x边，每个新边权重为1，然后运行BFS。我会得到一棵新的BFS树，因为它是一棵树，所以从根节点到每个其他顶点只有1条路径。 我遇到的问题是试图对以下算法进行分析。每个边都需要访问一次，然后根据其权重划分为相应数量的边。然后我们需要找到新图的BFS。 访问每条边的成本是O（m），其中m是每一条边访问一