modify section 'connection to successive shortest path algorithm'

alemini18 · adamant-pwn · commit d6bc9bc30423 · 2023-12-13T14:10:34.000+01:00
diff --git a/src/graph/hungarian-algorithm.md b/src/graph/hungarian-algorithm.md
@@ -251,7 +251,7 @@ For every step of the main algorithm:
 - Use [Dijkstra](dijkstra.md)'s algorithm to find the shortest-paths subgraph of the original network.
 - Update potentials for the next iteration.
 
-Given this description, we can observe that there is a strong analogy between $h(v)$ and potentials. It can be shown that, after reweighting, the set of all zero-weight edges represents the shortest-path subgraph where the main algorithm tries to increase the flow. This also happens in the Hungarian algorithm: we create a subgraph made of rigid edges (the ones for which the quantity $A[i][j]-u[i]-v[j]$ is zero), and we try to increase the size of the matching.
+Given this description, we can observe that there is a strong analogy between $h(v)$ and potentials: it can be checked that they are equal up to a constant offset. In addition, it can be shown that, after reweighting, the set of all zero-weight edges represents the shortest-path subgraph where the main algorithm tries to increase the flow. This also happens in the Hungarian algorithm: we create a subgraph made of rigid edges (the ones for which the quantity $A[i][j]-u[i]-v[j]$ is zero), and we try to increase the size of the matching.
 
 In step 4, all the $h(v)$ are updated: every time we modify the flow network, we should guarantee that the distances from the source are correct (otherwise, in the next iteration, Dijkstra's algorithm might fail). This sounds like the update performed on the potentials, but in this case, they are not equally incremented.
 
