Can we apply the Bellman-Ford algorithm to an Undirected Graph?

algorithm data-structures graph graph-algorithm bellman-ford
anuj pradhan picture anuj pradhan · Feb 9, 2013 · Viewed 15.5k times · Source

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?

Answer

mikyra picture mikyra · Feb 11, 2013

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.

Related questions

How to find if a graph is bipartite?

I have been trying to understand the bipartite graph. To my understanding it is a graph G which can be divided into two subgraphs U and V.So that intersection of U and V is a null set and union …

Read More
How to keep track of depth in breadth first search?

I have a tree as input to the breadth first search and I want to know as the algorithm progresses at which level it is? # Breadth First Search Implementation graph = { 'A':['B','C','D'], 'B':['A'], 'C':['A','E','F'], …

Read More
What exactly is augmenting path?

When talking about computing network flows, the Algorithm Design Manual says: Traditional network flow algorithms are based on the idea of augmenting paths, and repeatedly finding a path of positive capacity from s to t and adding it to the …

Read More