graph

Bellman-ford algorithm Bellman ford algorithm works on directed graph only ( if you want to use it on undirected graph then you will have to convert the undirected graph into directed graph first) Bellman ford algorithm is used to find the single source shortest path even when the graph has negative cycle(inwhich case Dijkstra's fails) Bellman ford also helps us check if the graph(DAG) has negative edge cycle What needs to be done: Relaxation of edges: if(distance[u] + weight < distance[v]){ distance[v] = distance[u] + weight; } Enter fullscreen mode Exit fullscreen mode This above check needs to be done…