具体图和关于最短路径的一些主张？
我陷入了一个具有挑战性的问题，我在笔记上阅读。
给出了一个无向加权连通图G(负权且所有权distinction),在该图中任意两个顶点之间的最短路径在(MST)上。（对于任何一对顶点和它们之间的任何最短路径，它都位于MST上）。以下哪个为真？
1）图G是树。
4）假设从顶点s、Prime（用于计算MST）和Dijkstra（用于计算最短路径）开始，以相同的顺序处理和添加顶点到它们的树中（两种算法处理和添加节点的顺序相同）
如何才能验证我这些选项？这是一个具有挑战性的问题。
共有1个答案
>
否。例如:V={1,2,3}，E={（1,2,1）,（2,3,2）,（1,3,4）}（每个边编码为元组（一个顶点，另一个顶点，权重））。它不是一棵树，但所有的最短路径都在最小生成树上。
是的。如果该边的权重小于最短路径中最重边的权重，则该边比最短路径短（因为没有负权重的边）。因此，最短的路径并不是最短的。这是一个矛盾。
没有*。假设我们有一个图，它有两个顶点{1,2}和它们之间的一条零权边。第一个顶点和第二个顶点之间存在无限多条最短路径([1,2],[1,2,1,2],...)
-
我有一个一般性的问题，关于如何在边没有权的无向图中找到最短路径和最长路径。 我们需要使用DFS算法来寻找图中的最长路径，而我们需要使用BFS算法来寻找图中的最短路径，这是一个正确的结论吗？
-
我试图解决的问题是： 给出一个图，其中每个边都用红色或蓝色着色： a）给出了生成两顶点(s，t)之间经过最小数量红边的路径的算法。
-
以下是消费税： 在某些图的问题中，顶点可以有权代替边的权或增加边的权。设Cv是顶点v的代价，C(x，y)是边(x，y)的代价。该问题涉及到在图G中寻找顶点a和顶点b之间的最便宜路径，路径的代价是该路径上遇到的边和顶点的代价之和。 (a)假设图中每条边的权重为零（而非边的代价为∞)，假设所有顶点1≤V≤n（即所有顶点的代价相同），Cv=1。给出一个求从a到b最便宜路径的高效算法及其时间复杂度。 (b
-
给了我一个问题，上面写着： 给定一个具有整数权值（正负两种）的连通有向图，发展一种求两顶点之间最短路径的算法。 我想我可以使用最小生成树算法，比如Kruskal的算法，然后用Dijkstra的算法来证明，因为在MST中，每个顶点只有一条内边，Dijkstra的算法即使在负权值下也能工作。 这听起来像是共食吗？ 附注。我很难证明MST包含有向图的每个顶点的最短路径。
-
给出一个无向加权图G和两个顶点：开始顶点和结束顶点 什么是最有效的算法，找到从开始到结束的最短路径，并能够将恰好一条边的权重变为零？ 编辑：我知道dijkstra算法，但正如我所说，在这个问题中情况不同：我们可以将一条边变为零，
-
主要内容：最短路径算法在给定的图存储结构中，从某一顶点到另一个顶点所经过的多条边称为 路径。 图 1 图存储结构 例如在图 1 所示的图结构中，从顶点 A 到 B 的路径有多条，包括 A-B、A-C-B 和 A-D-B。当我们给图中的每条边赋予相应的权值后，就可以从众多路径中找出总权值最小的一条，这条路径就称为 最短路径。 图 2 无向带权图 以图 2 为例，从顶点 A 到 B 的路径有 3 条，它们各自的总权值是：
-
在一个加权有向图中，我需要找到两个结点s，t之间的最短路径。以下是限制： 权重可以为负值。 路径必须经过一个特定的边，让我们从节点u到V调用her e和shes。 输出路径必须简单，即我们只通过一个节点一次。 因为我希望它最短，所以我将检查在从s到u之前从v到t运行bellman ford是否比相反的方式更快（如果有节点，两个节点都使用where是放置它的最佳位置）。 谢谢你的帮助！
-
我试图用BFS找到无向加权图的单源最短路径算法。 我想出了一个解决方案，将每个边权重转换成顶点之间的x边，每个新边权重为1，然后运行BFS。我会得到一棵新的BFS树，因为它是一棵树，所以从根节点到每个其他顶点只有1条路径。 我遇到的问题是试图对以下算法进行分析。每个边都需要访问一次，然后根据其权重划分为相应数量的边。然后我们需要找到新图的BFS。 访问每条边的成本是O（m），其中m是每一条边访问一