Queue-based Bellman-Ford algorithm

Question

i'm trying to understand how this algorithm works.

given a question to search the paths from a source s to all the vertices in the graph ,

I thought that i have to proceed as follows:

if no cycle in the graph: 
     topological sort of the graph 
     one iteration to calculate the shortest path

else if there is a cycle in the graph:
     put s in the queue 
     v=q.deque
     while q is not empty
        relax v

My question are :

Is my proceeding good or i have to change it.

When i must check that there is a negative cycle? Thank you

Answer 1

Your code for the acyclic one seems correct but depends on what do you mean by one iteration to calculate the shortest path.. If the graph is acyclic (i.e., a DAG) then topological sort will allow us to visit each vertex v once (after examining all of its predecessors) and update dist[v] to its minimum distance. This is done in linear time O(V+E). So your DAG algorithm should look somehow similar to this

  DAG_CASE:   
  topological sort of V
  for each u\in V following the topological sorting
    for each edge (u,v)
      relax(u,v) 

For the code of directed cyclic graphs (with no negative cycles), you are not relaxing an edge and not updating/checking its end points.. I am not familiar with the queued version of the BF algorithm. All I can say is that you need to make sure that a vertex v is in the queue whenever you realize that one of its predecessors (i.e. u) is not done yet. So your code should enqueue and dequeue some vertices under certain conditions (while relaxing the edges). I think you already know the non-queued version of the algorithm which is obvious.

When i must check that there is a negative cycle?

BF algorithm over a source s returns either the shortest paths from s to every other vertex or a failure indicating that there is a negative cycle. Following execution, If there is an edge that is not relaxed then there is a negative cycle.

Answer 2

I don't remember details of Bellman-Ford, but basically, assume you have n edges and m vertex,

for e = 1 to n-1
     iterate tru each vertex and apply the formula

This part can be found on the internet easily.

Related to When i must check that there is a negative cycle?, you will do one more iteration and if any value in the last array(the array after n-1-th iteration) changes, you will say there is negative cycle, if nothing changes, it indicates there is no negative cycle.

This youtube link explains Bellman-Ford well with an example.