if distance[u] + w < distance[v]: distance[v] := distance[u] + w predecessor[v] := u // Step 3: check for negative-weight cycles for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: error "Graph contains a negative-weight cycle" return distance[], predecessor[] " data-snippet-id="ext.88345ec5d94e5d4c5b8b3ca740900645" data-snippet-saved="false" data-codota-status="done"> function BellmanFord(list vertices, list edges, vertex source) ::distance[],predecessor[] // This implementation takes in a graph, represented as // lists of vertices and edges, and fills two arrays // (distance and predecessor) with shortest-path // (less cost/distance/metric) information // Step 1: initialize graph for each vertex v in vertices: distance[v] := inf // At the beginning , all vertices have a weight of infinity predecessor[v] := null // And a null predecessor distance[source] := 0 // The weight is zero at the source // Step 2: relax edges repeatedly for i from 1 to size(vertices)-1: for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: distance[v] := distance[u] + w predecessor[v] := u // Step 3: check for negative-weight cycles for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: error "Graph contains a negative-weight cycle" return distance[], predecessor[] f