A shortest path then uses at most |V| − 1 edges, and after k passes every distance whose shortest path uses at most k edges is correct.

After |V| − 1 passes every edge has been relaxed |V| − 1 times, which is enough for any graph at all.

It is a safety margin; half as many passes would always do.

|V| − 1 is the largest number of negative edges a graph can have without a negative cycle.

Each pass changes at least one distance, so |V| − 1 passes change |V| − 1 of them.

Θ(M + N)

Θ(M·N)

Θ(M) — it does not depend on N at all.

Θ(M·log N)

Θ(N)