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
Relax edge operation
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.