So the running time of the main while loop, ignoring any kind of pre processing or initialization is proportional to what I am gonna call NS and MS which is the number of nodes that can be reached from S and number of edges that can be reached from S. And the reason for this claim it just becomes clear if you inspect the code which we'll do in a second. 