Theorem 2.22. For a network with n nodes and m ares, the Bellman-Ford algorithm has running time O( n- + mm), which is O(am) ifm > n-1. Since there are less than n- arcs in a network we also have m = Ofn ), and so this running time is also O (n )