我们可以将Bellman-Ford算法应用于无向图吗？

问题描述

我知道Bellman-Ford算法适用于有向图。它会适用于无向图吗？看起来，对于无向图，它将无法检测周期，因为并行边将被视为周期。这是真的还是不？算法是否可以应用？

解决方案

事实上，任何无向图也是有向图。 b
$ b

你只需要指定任何边{u，v}两次（u，v）和（v，u）。

但不要忘记，这也意味着任何具有负重量的边缘都会被视为一个循环。
由于Bellman-Ford算法仅适用于不包含任何具有负权重的循环的图形，这实际上意味着您的无定向图形不得包含任何具有负权重的边。

如果使用贝尔曼 - 福特不是很好。

I know that Bellman-Ford Algorithm works for directed graphs. Will it will work for an undirected graph? It seems that with an undirected graph, it will not be able to detect cycles because parallel edges will be considered cycles. Is this true or not? Can the algorithm be applied?

解决方案

As a matter of fact any undirected graph is also a directed graph.

You just have to specify any edges {u, v} twice (u, v) and (v, u).

But don't forget, that this also means any edge with a negative weight will count as a loop.As the Bellman-Ford algorithm ONLY works on graphs that don't contain any cycles with negative weights this actually means your un-directed graph mustn't contain any edges with negative weight.

If it doesn't its pretty fine to use Bellmann-Ford.

这篇关于我们可以将Bellman-Ford算法应用于无向图吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！