在具有正边缘和负边缘的有向图中找到从源到目的地的最短路径,使得在路径中的任何点处,在其之前的边缘的总和为负.如果不存在这样的路径也报告.

我试图使用改良的Bellman Ford,但找不到正确的解决方案.

我想澄清几点:

1. 是的,可以有负重量循环.
2. n是边数.
3. 假设问题有解,则存在O(n)长度路径.
4. + 1/-1边缘权重.

这是一个消费税:

要么证明以下内容,要么给出一个反例:

(a)无向图的最小生成树中的一对顶点之间的路径是否必须是最短(最小权重)路径？

(b)假设图的最小生成树是唯一的.在无向图的最小生成树中,一对顶点之间的路径是否必须是最短(最小权重)路径？

我的回答是

(一个)

不,例如,对于图0,1,2,0-1是4,2-2是2,2-0是5,那么0-2的真正最短路径是5,但是mst是0-1-2 ,在mst,0-2是6

(b)中

我的问题进入了这个(b).

我不明白怎么whether the MST is unique会影响最短的路径.

首先,我的理解是,当边的权重不明显时,可能同时存在多个MST,对吧？

其次,即使MST是唯一的,上述(a)的答案仍然适用于(b),对吧？

我三天前参加了奥林匹克考试.我遇到了一个很好的问题如下.

我们知道bellman-ford算法会检查每个步骤中的所有边缘,对于每个边缘,如果,

d(v)的> d(U)+ W(U,V)

然后d(v)被更新,这w(u,v)是边缘的权重,(u, v)并且d(u)是顶点的最佳查找路径的长度u.如果在一步中我们有no update for vertexes算法terminate.假设这个算法,用于在迭代完成后s用n顶点找到图G中顶点的所有最短路径,k < n以下哪个是正确的？

1)所有最短路径中的边缘数量s最多k-1

2)所有最短路径的权重s最多k-1

3)图形没有负循环.

谁可以讨论这些选项？

Red Dot - Represents the initial location
Black Dot - Already occupied
Green - Free to occupy
Destination - Boundry of the matrix [which means either x = 0 or y = 0 or x = 8 or y = 8]

例:

它red dot可以一次只放置一个动作,并且可以移动到连接到它的绿色六个圆圈中的一个.计算这种迷宫中最短路径的最快方法是什么.

这只是我自己想出来的东西,但它似乎是一个有趣的问题而且让我难过.

在二维空间中有一组点,其中一个点指定为"开始",一个指定为"结束".每个点都有坐标(以距离原点为单位),但也有"加速度数"(以米 - 秒为单位的Δ-V).到达某个点(包括开始点)后,您可以在任何方向上加速到该点的加速度数.边缘成本取决于您当前的速度,但您还必须朝着正确的方向前进.

是否有一种有效的算法来寻找到达终点的最快路径？我没有提出比"尝试每条路径并检查结果"更好的东西.Djikstra和其他简单的算法不起作用,因为你不能轻易地说中间点的一条路径比另一条路径更好或更差,如果它们以不同的初始速度到达.

如果这太简单了,如果你添加了必须在终点停止的要求怎么办？(即,当你到达终点时,你必须小于它的加速度值.)

编辑:要明确,方向很重要.在遍历图形时保持速度矢量,加速意味着向其添加矢量,其大小以该点的加速度数量为上限.这意味着在哪里建造了一个巨大的速度是有害的,因为你会走得太快,以"引导"对其他宝贵的意见/目的地的情况.

我正在寻找一种方法来实时找到巨大图形中节点之间的最短路径.它有数十万个顶点和数百万个边.我知道之前已经问过这个问题,我想答案是使用广度优先搜索,但我更感兴趣的是知道可以用什么软件来实现它.例如,如果已经存在用于在无向图中执行bfs的库(使用python绑定!),那将是完全完美的.

我正在尝试使用优先级队列来实现dijkstra算法,但我无法理解它是如何工作的.我在网上阅读了很多指南,但我根本无法理解这个算法.

我的问题是:每个节点的优先级是什么？我认为它是最小值的传入边缘的权重,但我不确定.这是真的？

第二个问题,当我提取队列的根时,如果该节点不与没有一个被访问节点相邻,那么该如何工作？

正如标题所说,我正在尝试实现一种算法,该算法找出给定图形中所有节点对之间的距离.但还有更多:(可能有助于你的事情)

• 图表未加权.这意味着可以将所有边缘视为权重为1.
• |E| <= 4*|V|
• 图表非常大(最多144个深度)
• 该图是针对性的
• 可能有周期
• 我正在用python编写我的代码(如果你引用算法,那么代码也会很好:))

对于所有对,我都知道约翰逊的算法,Floyd-Warshal和Dijkstra.但是当图表具有权重时,这些算法是好的.

我想知道我的情况是否有更好的算法,因为这些算法用于加权图.

谢谢!

我有一个加权图,没有负权重,我想找到从一个节点到另一个节点的路径,试图最小化单步的成本.我不需要最小化旅行的总成本(例如Dijkstra),而是平均步骤成本.但是,我有一个约束:K,路径中的最大节点数.

所以例如从A到J可能Dijkstra会找到这条路径(括号之间的重量)

A (4) D (6) J -> total cost: 10

我需要的算法,设置K = 10,会找到类似的东西

A (1) B (2) C (2) D (1) E (3) F (2) G (1) H (3) J -> total cost: 15

这个问题有没有众所周知的算法？

提前致谢.

欧亨尼奥

编辑为templatetypedef的答案.一些问题:

1)事实上它可能多次采取一个周期来降低平均值对我的问题不利:也许我应该提到它但我不想多次访问同一个节点

2)是否有可能利用我没有负权重的事实？

3)当你说O(kE)时,你是指整个算法还是只是附加部分？

让我们在C中采用这个简单的实现,其中n =节点数e =边数,d是具有距离的向量,具有前驱的pa向量和结构边(u,v,w)记忆图中的边

for (i = 0; i < n; ++i)
    d[i] = INFINITY;

    d[s] = 0;

    for (i = 0; i < n - 1; ++i)
        for (j = 0; j < e; ++j)
            if (d[edges[j].u] + …

假设我有10分.我知道每个点之间的距离.

我需要找到通过所有点的最短路线.

我已经尝试了几种算法(Dijkstra,Floyd Warshall,......),它们都给了我开始和结束之间的最短路径,但是它们没有制作一条包含所有点的路线.

排列工作正常,但它们太耗资源.

您可以建议我使用哪些算法来研究这个问题？或者是否有记录的方法使用上述算法执行此操作？