Djikstra solves the shortest circuit with negative weight

This article blog Very good

Set a potential function at each point $h_i$, And let the edge weight of the new graph $w_{i,j}^{\prime }=w_{i,j}+h_i-h_j$, requirement $w_{i,j}^{\prime }\ge 0$
Original picture $1\to n$ The shortest path of is equal to the new graph $1\to n$ The shortest path of minus $h_1-h_n$

How to maintain $h_i$：
Yes $h_i$ For any edge with flow $(i,j)$,$h_i+w_{i,j}\ge h_j$
This is similar to the shortest path trigonometric inequality $di{s}_i+w_{i,j}\ge di{s}_j$
At the beginning, if the edge weight is not negative, it is all set 0
Otherwise, you can run once SPFA, Make $h_i=di{s}_i$. If it's a DAG You can push $h_j=\min h_i+w_{i,j}$.

After running Zengguang Road, some edges will be added , Suppose that $(i,j)$, Produced $(j,i)$：
First of all, there must be $di{s}_i+h_i-h_j+w_{i,j}=di{s}_j$ （ With $S$ For the source point ）
Change to $(di{s}_i+h_i)+w_{i,j}=(di{s}_j+h_j)$
So make the new $h_i^{\prime }=h_i+di{s}_i$ To satisfy the newly added edge .

And for the original edge , Because of $di{s}_i+h_i-h_j+w_{i,j}\ge di{s}_j$, Easy to get $h_i^{\prime }$ Still meet the conditions .

If the $T$ Take the shortest path of the reverse side for the source point , Make $w_{i,j}^{\prime }=w_{i,j}+h_j-h_i$ that will do ,$h_i^{\prime }$ Still add... Every time $di{s}_i$.