technique used to transform a graph by changing the weights of its edgesreweighting is used to transform the input graph into a new graph with non-negative edge weightsreweighting causes the length of every path to strictly increase