我们可以将行李员Ford算法​​，以无向图 [英] Can we apply Bellman ford algorithm to Undirected Graph

问题描述

我知道，Bellman-Ford算法​​适用于有向图，但只是为信息，我想知道它是否会为联合国向图？因为与取消向图它将不能够检测周期，因为平行边缘将被认为是循环!!。请澄清。

I know that Bellman-Ford Algorithm works for directed graphs but just for Info i want to know that whether it will work for Un-directed graph? Since with Un-directed graph it will not be able to detect cycles because parallel edges will be considered as Cycles!!. Please clarify.

推荐答案

由于事实上任何无向图也有向图。

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

您只需要指定任何边缘{U，V}两次（U，V）和（V，U）。

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

但不要忘了，这也意味着有负重量的任何优势将计为一个循环。 由于Bellman-Ford算法​​只适用于图形不包含具有负权重的任何周期这实际上意味着您未向图中不得包含任何边缘与负重量。

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.

如果它不其pretty的罚款使用Bellmann福特。

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

这篇关于我们可以将行李员Ford算法​​，以无向图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！