The link is only as strong as it's weakest... link? Anyway, given the structure of internet, I wouldn't say it is O(N*M), more like O(the number of major ISPs).

Well all endpoints might differ but the links might rely on the exact same algorithm so you need to count distinct links