terminologies

Directed acrylic graph

known as DAG, a directed graph without any cycle.

Tense edge

If this edge can be improved the destination vertex shortest walk estimation

$$(\forall u\to v)u.dist+w(u\to v)<v.dist$$

Relax edge operation

$$(\forall u\to v)u\to v\text{ is tense}⟹v.dist:=u.dist+w(u\to v)$$

Negative cycle

Negative weight cycles make shortest paths undefined for any algorithm, as we can decrease cost infinitely by repeating the cycle.
Additionally, negative edge weights break Dijkstra’s greedy assumption.