Unit 5: More on Dynamic Programming - Subjective Questions

The all-pairs shortest-path (APSP) problem finds the shortest-path distance between every ordered pair of vertices in a weighted graph .

For vertices, the output is usually an distance matrix , where is the minimum cost of a path from vertex to vertex .

• when no relevant negative cycle exists.
• if is unreachable from .
• Negative edge weights are permitted by algorithms such as Floyd-Warshall.
• A reachable negative-weight cycle makes a finite shortest path undefined because the cycle can be traversed repeatedly to reduce the path cost.

APSP may also produce a predecessor or next-vertex matrix so that the actual shortest paths can be reconstructed.

A shortest path has the following optimal-substructure property: every subpath of a shortest path is itself a shortest path between its endpoints.

Suppose a shortest path from to passes through an intermediate vertex . The path can be divided into:

• a shortest path from to , and
• a shortest path from to .

If either subpath were not shortest, replacing it with a shorter one would produce a path from to shorter than the assumed shortest path.

Floyd-Warshall uses this property by considering two possibilities for each pair :

1. The shortest path does not use as an intermediate vertex.
2. It uses , in which case its cost is the sum of the shortest distances from to and from to .

Number the vertices from to . Let denote the length of a shortest path from to whose intermediate vertices are restricted to the set .

For , no intermediate vertex is allowed:

When vertex becomes available, a shortest path from to either:

• does not use , with cost , or
• uses , with cost .

Therefore,

After processing all vertices, is the all-pairs shortest-distance matrix.

The Floyd-Warshall algorithm initializes a distance matrix from the graph and repeatedly permits one additional intermediate vertex:

1. Initialize .
2. Set for each edge .
3. Set all remaining entries to .
4. For to , update every pair using
   

The loop must be outermost because, during iteration , matrix entries must represent paths whose intermediate vertices belong to . Interchanging the loops arbitrarily can violate this invariant.

Complexity:

• The three nested loops give a running time of .
• The distance matrix requires space.
• Updating the matrix in place is valid, so separate matrices for every value of are unnecessary.
• A path-reconstruction matrix, if maintained, requires an additional space.

The initial matrix represents paths with no intermediate vertices:

• Set for every vertex .
• For an edge of weight , set .
• If there is no edge from to and , set .
• For parallel edges, use the minimum edge weight.
• Negative edges can be stored normally; Floyd-Warshall does not require nonnegative edge weights.

If a negative self-loop exists, its negative weight should be retained instead of replacing it with zero. More generally, initialization can use

Arithmetic involving must be guarded in an implementation so that adding a finite value to a sentinel used for infinity does not overflow.

In addition to the distance matrix, maintain a next matrix. Initially:

• If an edge from to exists, set .
• If is unreachable from , leave undefined.

Whenever Floyd-Warshall improves a distance through ,

perform both updates:

To reconstruct the path from to , begin at and repeatedly replace the current vertex by until is reached.

• If is undefined, no path exists.
• Reconstruction takes time for a path containing edges.
• The next matrix occupies additional space.
• Paths affected by a reachable negative cycle must not be reported as ordinary finite shortest paths.

After Floyd-Warshall finishes, inspect the diagonal entries of the distance matrix. A negative-weight cycle exists if

for at least one vertex .

A negative diagonal value means that there is a path from back to itself with negative total cost. Repeating this cycle can make the path cost arbitrarily small.

The effect is not necessarily limited to the cycle vertices. The shortest distance from to is undefined if there is a vertex such that:

• can reach ,
• , and
• can reach .

Such pairs may be marked with to show that no finite minimum exists. Other vertex pairs not connected through the negative cycle can still have valid finite distances.

Floyd-Warshall:

• Time: .
• Space: .
• Allows negative edges.
• Detects negative cycles.
• Is simple and effective for dense graphs.

Repeated Dijkstra:

• Run Dijkstra once from each vertex.
• With a binary heap, the total time is approximately .
• It is attractive for sparse graphs.
• It requires nonnegative edge weights unless reweighting, as in Johnson's algorithm, is used.

Repeated Bellman-Ford:

• Running Bellman-Ford from every source takes time.
• It permits negative edges and can detect reachable negative cycles.
• It is generally slower than Floyd-Warshall for dense graphs.

Thus, the best method depends on graph density, edge-weight restrictions, and whether path or negative-cycle information is required.

Let be the weighted adjacency matrix. In the min-plus algebra, ordinary addition is replaced by minimum, and ordinary multiplication is replaced by addition.

For matrices and , their min-plus product is

If is the minimum weight of a path from to using at most edges, then extending paths gives

A shortest simple path contains at most edges when no relevant negative cycle exists. Therefore, computing solves APSP.

• Repeated extension takes with the direct method.
• Repeated squaring reduces this to using the standard cubic min-plus product.
• Floyd-Warshall is usually preferable with its running time.

Initialize missing edges to and diagonal entries to zero. Successive improvements include:

• through vertex : .
• through vertices : .
• through vertex : .
• through vertices : .
• through vertex : .
• through vertices : .
• through vertex : .
• through vertices : .

The final shortest-distance matrix is

Every diagonal entry remains zero, so this graph contains no negative-weight cycle.

An optimal binary search tree (OBST) is a binary search tree constructed from sorted keys so that the expected search cost is minimized for known access probabilities.

Let the ordered keys be . Let:

• be the probability of a successful search for .
• be the probability of an unsuccessful search in the gap represented by dummy key , where .

The tree must preserve the binary-search-tree ordering. Its expected cost is

An OBST minimizes this expected cost rather than minimizing only tree height or worst-case search time.

For sorted keys , two types of probabilities are used:

• Successful probability : the probability that a search is made for the existing key .
• Unsuccessful probability : the probability that a search value lies in a gap between existing keys.

The dummy key represents values less than , represents values greater than , and represents values between and .

Normally,

The values matter because an unsuccessful search still follows a root-to-leaf route and performs comparisons. Ignoring them can therefore produce a tree that is not optimal for the actual search distribution.

The expected cost is the probability-weighted number of nodes examined during successful and unsuccessful searches.

If the root has depth zero, the expected cost is

The extra counts the comparison or level associated with reaching a key or dummy leaf.

For example, moving an entire subtree one level deeper increases its expected cost by the sum of all successful and unsuccessful probabilities in that subtree. This observation explains why the OBST recurrence adds the interval weight whenever a root is selected.

A frequently accessed key should generally occur near the root, but choosing the largest-probability key as the root is not always globally optimal because key order and the costs of both subtrees must also be considered.

Let be the minimum expected cost of a subtree containing keys through . Let

be the total probability associated with that subtree.

If is selected as the root, then:

• keys through form the left subtree,
• keys through form the right subtree, and
• every item in both subtrees moves one level deeper, adding to the expected cost.

Thus, the cost for root is

Minimizing over all possible roots gives

The base case is

A separate table stores the minimizing root for each interval so that the optimal tree can be reconstructed.

An empty subtree between keys is represented by a dummy key. Therefore, for :

The tables are filled by increasing interval length:

1. Initialize all empty intervals.
2. For lengths , set .
3. Compute
   
4. Try every root from through .
5. Store the minimum cost in and its root in .

Increasing-length order is essential because evaluating interval requires the already-computed smaller intervals and . The final minimum expected cost is .

The standard algorithm maintains three tables:

• : minimum expected cost for keys through .
• : total probability in that interval.
• : root index producing the minimum cost.

For every interval , it evaluates each possible root and computes

If is smaller than the current value, the algorithm stores and .

There are intervals and up to root candidates per interval. Therefore:

• Time complexity: .
• Space complexity: .

To reconstruct the tree, choose as the overall root. Recursively use for the left subtree and for the right subtree. An empty interval becomes the corresponding dummy leaf.

The probabilities sum to . Initialize empty-subtree costs using the values.

For one-key intervals:

For interval , :

• Root : .
• Root : .

Hence, with root .

For interval , :

• Root : .
• Root : .

Hence, with root .

For all keys, :

• Root : .
• Root : .
• Root : .

Therefore, the optimal tree has as root, as its left child, and as its right child. Its expected search cost is .

The standard OBST algorithm tries every possible root for every interval, giving time. Knuth's optimization uses the monotonicity of optimal root indices:

Therefore, while solving interval , it is sufficient to test roots only in the range

rather than testing every from through .

For the classical OBST cost satisfying the required quadrangle-inequality and monotonicity conditions, the total number of tested candidates over all intervals becomes quadratic.

• Optimized time complexity: .
• Space complexity: .

The recurrence and resulting optimal tree remain unchanged; only the range of root candidates examined by the algorithm is reduced.

Optimal binary search tree:

• Preserves the sorted order of keys.
• Minimizes expected search cost using access probabilities.
• May be structurally unbalanced when probabilities are highly unequal.

Height-balanced binary search tree:

• Keeps height at .
• Provides good worst-case search time.
• Usually ignores unequal access probabilities and may not minimize expected cost.

Huffman tree:

• Produces an optimal prefix code for weighted symbols.
• Places high-frequency symbols near the root.
• Does not generally preserve the sorted or alphabetic order required by a binary search tree.
• Usually models successful symbol occurrences rather than ordered successful and unsuccessful searches.

Thus, balancing optimizes structural height, Huffman coding optimizes prefix-code length without a search-order constraint, and an OBST optimizes expected ordered-search cost.

Assumptions:

• Keys have a fixed sorted order.
• Successful probabilities and unsuccessful probabilities are known or can be estimated.
• The probability distribution is sufficiently stable.
• Search cost is modeled primarily by node depth or number of comparisons.

Applications:

• Static dictionaries and symbol tables.
• Compiler keyword or identifier lookup.
• Read-heavy databases with stable query frequencies.
• Decision structures where outcomes must remain ordered.

Limitations:

• If access frequencies change, the stored tree may cease to be optimal.
• Standard construction uses space and time unless optimized.
• The model may not reflect cache behavior, storage pages, update costs, or hardware-specific comparison costs.
• Frequent insertion and deletion can invalidate the optimal structure.

For dynamic workloads, self-adjusting or balanced trees may be more practical even when their theoretical expected search cost is not minimal.