如何找到无向边加权图从顶点v到顶点w的最短路径？
给定一些无向边加权图，什么算法可以用来找到从某个顶点v到另一个顶点w的最短路径？
对于有向边加权图，可以使用Dijkstra的最短路径算法，但我使用的是无向图，所以它不起作用。
对于非边加权的图，可以使用广度优先搜索（BFS），但我使用的是边加权图，所以它不起作用。
既然它是无向和边加权的，一般最短路径法是什么？
共有1个答案
Dijkstra的单源最短路径算法可以应用于无向图和有向图。唯一的规定是边缘权重必须是非负的。从图中的单个顶点v开始，v被弹出到集合S中。该算法检查S中尚未存在的每个相邻顶点，拾取权重最小的边，然后将该顶点弹出到S中。顶点v到S中每个相邻顶点的距离根据边权重更新。一旦遍历了整个图，就确定了每个节点之间的最短路径。
例子：https://brilliant.org/wiki/dijkstras-short-path-finder/
此外，在加权边图上执行BFS被证明是棘手的。请看这篇关于推理的文章。
-
在无向赋权图中寻找两个顶点之间的最短路径。还已知权重是小于log（logV）的整数，其中V是顶点的数量。使用贝尔曼-福特或Dijkstra算法很容易解决，但是有没有什么算法可以更快地解决呢？ 到目前为止，我一直在考虑使用BFS，将权重大于1的边划分成两个权重为1的边，但如果V是大数，就不是一个好主意。不，这不是我的家庭作业，我只是在想。
-
以下是消费税： 在某些图的问题中，顶点可以有权代替边的权或增加边的权。设Cv是顶点v的代价，C(x，y)是边(x，y)的代价。该问题涉及到在图G中寻找顶点a和顶点b之间的最便宜路径，路径的代价是该路径上遇到的边和顶点的代价之和。 (a)假设图中每条边的权重为零（而非边的代价为∞)，假设所有顶点1≤V≤n（即所有顶点的代价相同），Cv=1。给出一个求从a到b最便宜路径的高效算法及其时间复杂度。 (b
-
下面的堆栈溢出问题 我尝试了在语句中使用两个重复的多个构造，但无法为每个起始顶点获得独立的。我也在使用平台，因此它限制了Gremlin的使用，其中不允许使用循环/脚本。所有gremlin查询必须以并由与链接在一起的命令组成 https://docs.aws.amazon.com/neptune/latest/userguide/access-graph-gremlin-differences.ht
-
我有一张室内地图上的无向位置图。当给定一组顶点时，我要找到覆盖所有这些顶点的最短路径。图形包含52个顶点和150-250条边。 我能用什么最好的算法来找到最短的路径。请不要混淆这是一个旅行推销员的问题。它不需要覆盖所有节点，只需要覆盖给定的节点集。
-
我试图弄清楚，如何计算具有加权顶点的图的最短路径。经典算法，如Dijkstra和Floyd-WarMarshall，通常使用加权边，我看不到如何将它们应用于我的情况（加权顶点）： 我的一个想法是将图形转换为带有加权边的更经典的视图。这是我收到的： 这里我们有单向和双向加权边，但我仍然不确定哪种算法可以处理这一点，以找到最短路径。
-
我们有一个边带正权的有向图G(V，E)，作为源顶点s，目标点T。此外，最短的s-t路径包括图中的每一个其他顶点。我需要计算s和t之间的交替最短路径距离，以防某些边e∈e被删除。我想设计一个O(e^2logV)算法，它计算图G\e中所有e∈e的最短S-T路径距离。最后的输出应该是一个大小为E的数组，其中edge E的条目应该包含G\E中最短的S-T路径距离。