Description
-
Consider a union- nd implementation that uses the same basic strategy as weighted quick-union but keeps track of tree height and always links the shorter tree to the taller one. Prove a logarithmic upper bound on the height of trees for N sites for this scheme.
-
Give a proof of correctness for Algorithm 4.10, for computing shortest paths in edge-weighted Directed Acyclie Graphs (DAGS). Use proof by contradiction technique.
-
If the PQ is implemented as an unsorted sequence, show that Dijkstra’s algorithm runs in O(n2) time. For what type of graphs is this implementation preferred?
-
If at the end of the execution of Bellman-Ford algorithm, there is an edge (u; z) that can be potentially relaxed (that is, D[u] + w(u; z) < D[z], then show that the input digraph G contains a negative-weight cycle.
1