从多个顶点到单个顶点的所有最短路径
下面的堆栈溢出问题
我尝试了在语句中使用两个重复的多个构造，但无法为每个起始顶点获得独立的存储('x')。我也在使用AWS neptune平台，因此它限制了Gremlin的使用，其中不允许使用循环/脚本。所有gremlin查询必须以g开始。并由与.链接在一起的命令组成
https://docs.aws.amazon.com/neptune/latest/userguide/access-graph-gremlin-differences.html
共有1个答案
该技术不能应用于多个起始顶点。但是，您可以从另一边开始，因为这是一个已知的顶点：
g.V(1343).store('x').
repeat(__.in().where(without('x')).aggregate('x')).
until(hasLabel('label')).
path()
如果其中一个开始顶点可以是另一个开始顶点路径的一部分，那么您可能不会在潜在的开始顶点处中断，而是这样做：
g.V(1343).store('x').
repeat(__.in().where(without('x')).aggregate('x')).
emit(hasLabel('label')).
path()
-
我们有一个边带正权的有向图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路径距离。
-
我怎样才能找到一个有向图中的所有顶点，这样每一个顶点都可以从这个顶点到达呢？现在我只能“发明”O(v^3)ALGO--从每个顶点得到一个DFS/BFS，但我确信，有一个更快的方法来解决这个问题。 谢谢你！
-
因此，如果我在一个图中有两个顶点，它们通过一个以上的边连接，而它们之间有相同的最短路径（即，如果我有节点a和节点B，它们直接通过三条边连接（它们之间有三条最短路径，每个距离为1)，所以计数应该返回3）我该如何修改BFS算法来实现这一点？这是我的代码，它只计算2个节点之间的最短路径，而不计算这些最短路径的个数。
-
我正在尝试编写一个算法，该算法将重建Floyd-Warshall算法中所有顶点对之间的最短路径（如果有，则为最短路径绑定多条路径）。我从这个问题中得到了一些提示：https://stackoverflow.com/a/11371588/7447425 基于此，我修改了Floyd Warshall算法： 该图是边缘列表的形式，例如： 到目前为止，一切似乎都很顺利。 对于路径重建， 但这不管用。那么，
-
枚举任意图中两个顶点之间的所有简单路径通常需要指数时间，因为顶点之间可能存在指数数量的简单路径。但是如果我们只对两个endpoint顶点之间至少一条简单路径上的顶点感兴趣呢？ 也就是说：给定一个无向图和两个不同的顶点，是否有多项式时间算法可以找到两个顶点之间至少一条简单路径上的每个顶点？这与连通性不同；不包括死胡同和死胡同。然而，分支和连接路径是允许的。 我发现编写一个看起来可以解决这个问题的算法
-
以下是消费税： 在某些图的问题中，顶点可以有权代替边的权或增加边的权。设Cv是顶点v的代价，C(x，y)是边(x，y)的代价。该问题涉及到在图G中寻找顶点a和顶点b之间的最便宜路径，路径的代价是该路径上遇到的边和顶点的代价之和。 (a)假设图中每条边的权重为零（而非边的代价为∞)，假设所有顶点1≤V≤n（即所有顶点的代价相同），Cv=1。给出一个求从a到b最便宜路径的高效算法及其时间复杂度。 (b