function BellmanFord(list vertices, list edges, vertex source) ::weight[],predecessor[] // This implementation takes in a graph, represented as // lists of vertices and edges, and fills two arrays // (weight and predecessor) with shortest-path // (less cost/weight/metric) information // Step 1: initialize graph for each vertex v in vertices: if v is source then weight[v] := 0 else weight[v] := infinity predecessor[v] := null // Step 2: relax edges repeatedly for i from 1 to size(vertices)-1: for each edge (u, v) with weight w in edges: if weight[u] + w < weight[v]: weight[v] := weight[u] + w predecessor[v] := u // Step 3: check for negative-weight cycles for each edge (u, v) with weight w in edges: if weight[u] + w < weight[v]: error "Graph contains a negative-weight cycle" return weight[], predecessor[]
Read full article from Bellman–Ford algorithm - Wikipedia, the free encyclopedia
No comments:
Post a Comment