Bellman Ford Dynamic Programming

I have been learning graph algorithms, and the concept of dynamic programming is quite succinct. However, I read that Bellman Ford is a form of dynamic programming. I am not sure why since given so many unnecessary re-computations, it is not exactly efficient in the likes of other dynamic programming that computes the sub-problems bottom up to the final problem. For example, FloyWarshall has a well defined sub structure of considering all other vertices up to k.

But for Bellman Ford, the implementation is not really relying on any computed sub problems, it is just a brute force algorithm that correctly returns the shortest path but it is not correctly computing the sub-problems in some correct order needed by a dynamic programming algorithm?

Bellman ford – negative cycle

This is my code for detecting a negative cycle in a graph using bellman ford algorithm but I can’t figure out why it returns a wrong answer

public static final int INF = Integer.MAX_VALUE; private static int negativeCycle(ArrayList<Integer>[] adj, ArrayList<Integer>[] cost) {     int dep[] = new int[adj.length];     for(int i=0; i<adj.length; ++i)         dep[i] = INF;      dep[0] = 0;      for (int i = 0; i < adj.length-1; i++) {         for(int j = 0; j < adj.length; j++){             for (int v : adj[j]) {                 int v_index = adj[j].indexOf(v);                 if (dep[v] > dep[j] + cost[j].get(v_index)) {                     dep[v] = dep[j] + cost[j].get(v_index);                  }             }         }     }      for (int j = 0; j < adj.length; j++) {         for (int v : adj[j]) {             int v_index = adj[j].indexOf(v);             if (dep[v] > dep[j] + cost[j].get(v_index)) {                 return 1;             }         }     }      return 0; } 

Finding negative cycle using Bellman Ford

Given a graph with |V| vertexes and |E| edges, I have to find a negative cycle, if there is one, in a graph. The wanted complexity is O(|V|*|E|).

I was thinking about using Bellman-Ford to solve the question doing this: Do |V| iterations of Bellman-Ford, If there were no changes on the last iteration, there is no cycle of negative weight in the graph. Otherwise take a vertex the distance to which has changed, and go from it via its ancestors until a cycle is found. This cycle will be the desired cycle of negative weight.

The problem is, that no start vertex is given, and Bellman-Ford notes wether there is reachable negative cycle via the start vertex or not. Assume that if we start from vertex a there won’t be negative cycle and if the start vertex was b there will be one. So if I choose a as a start vertex I’ll miss the negative graph.

How can I solve that? I thought about trying all the vertexes as start vertex but it won’t be O(|E|*|V|).

why not use dijkstra algo + last line of bellman ford instead of bellman ford

correct me if wrong 1.for a given graph apply dijkstra on it. after v-1 iterations or after all possible minimal distances for every node have been found. 3.check for every edge(u,v) in the graph if(v.d>u.d+w(u,v)) then return false here time complexity will be lesser than bellman ford and also negative cycles will be taken care of