Consider a weighted undirected graph G=(V,E), where V is the set of nodes and E is the set of edges. Every edge (v,w) between nodes v and w has an associated cost denoted by c(v, w). In the graph, u is an arbitrarily chosen node. Analyze the complexity (using O-notation) of the following algorithm that runs on the graph: Initialization:

N' = {u} for all nodes v in V if v adjacent to u

then D(v) = C (u, v) else D(v) = infinity

Loop

find w not in N' such that D(w) is a minimum

add w to N'

update D (v) for all v adjacent to w and not in N' :

D (v) = min ( D(v) , D(w) + c (w, v) )

/* new cost to v is either old cost to v or known shortest path cost to w plus cost from w to v */

until all nodes in N'