Time complexity of the generic algorithm for finding shortest path in a graph

I am studying MIT's introduction to algorithms course, and I came across the analysis of the time complexity for a generic algorithm for finding the shortest path in a graph.

here is the pseudocode of the algorithm:

and here is the relaxation process on a graph:

I just could not understand why does relaxation process takes exponential time in the worst case as expressed by the O(2 ^(N/2)).