sayeed_1999's blog

About shortest path/negative cycle on Bellman ford algorithm
By sayeed_1999, history, 4 years ago, In English

The algorithm computes from one source vertex the whole thing.

If i want to detect negative cycles in a graph using bellman ford, if i assume vertex 1 as the source, and no edge comes out of the vertex 1 in that test set, it wont work.

how will you consider source vertex in these cases... to detect negative cycles

Asking for solutions..

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

If no edge comes out from source vertex, then it's not possible to reach any other vertex from this source. The algorithm will work as expected.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    I want to run bellman ford to detect negative cycles in a graph, in that case how will i choose the source. as i cant see which should be the source from the test set

    should i consider all vertices as source each time and run!?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      You can set the initial distance to every node as 0 and run the algorithm. This will be the same as creating a dummy node that goes to every vertex in the graph with 0 cost and using it as source vertex.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        Thank you so much!!

        This logic works fine considering a source from which no edge comes out!! O:)

        because in other sense all are the sources here when all are initially zero :p :p

        → Reply