1
$\begingroup$

I'm a little hung up on the Bellman-Ford algorithm. Here is my current understanding and some questions:

1) The root is defined as a source node that has only outgoing paths from it and the goal of the algorithm is to find a path from this source node to every other node in the graph G : there is a spanning, directed tree from the root.

2) There can only be one root and there must exist a path from the root to every other node in the graph G. Do we need to always assume this? It feels like we should have to make this assumption as our goal is to form a shortest path from the root to every other node in the graph and if there exists some node such that there is only an outgoing path from it and it isn't the source, then I don't think we'd be able to reach it. I just want to be sure that this is the case.

3) A sequence is formed during each pass of the algorithm and there will be a maximum of n-1 passes as there are n nodes and our goal is only to connect them analogous to a MST.

4) A sequence is an ordered set of nodes, starting from the root and branching outwards to depict the past from the root that was taken.

5) This is more of a question regarding the root, related to (1)... Can we arbitrarily assign a node as the root even if it has an inflowing arc and just ignore that inflow?

Am I on the right track in my understanding?

$\endgroup$

1 Answer 1

1
$\begingroup$

The selection of source node depends on you. You can choose any node to be your source irrespective of its non zero in-degree. The algorithm tries to generate the shortest path distance from your selected source node to all other nodes in the graph.

It is safe to assume that the graph is connected . For the same you can first run DFS over the graph to find the connected components. If the graph is connected then run Bellman Ford algorithm.

$\endgroup$
3
  • $\begingroup$ So in an instance where the graph is not connected to the source, can we run multiple Bellman Ford algorithms to connect the graph from each respective source node? I'm think of a specific example : r = the root in G, and there is a path rw connecting r to some node w but then there is a node a : there exists another path aw connecting a to w (a straight line of three nodes with both outer nodes pointing inwards towards the middle node). In cases like this, Bellman Ford wouldn't work with just one go, right? $\endgroup$
    – user370170
    Commented Oct 22, 2016 at 18:38
  • $\begingroup$ Bellman ford will work in one go. In directed graphs if a path doesn't exist between two nodes the algorithm is going to respond with the shortest path between them as infinity. Go through the Algorithm for directed graphs you will be quite clear about the crux then $\endgroup$ Commented Oct 23, 2016 at 3:19
  • $\begingroup$ Awesome, thanks. I started running through an example and saw right away what you were saying, thanks!! $\endgroup$
    – user370170
    Commented Oct 24, 2016 at 3:39

You must log in to answer this question.