Consider the following graph.

(a) Find (by inspection) shortest paths from all nodes to all other nodes.

(b) Verify that every subpath of the optimal 1 to 4 path in part

(a) is itself optimal.

(c) Detail your optimal solutions of part

(a) in functional notation n[k][/] and xi,j [k][/].

(d) Write functional equations for the shortest path problems of part (a).

(e) Verify that the n[k][/] of part

(c) satisfy functional equations of part (d).

(f) Explain why functional equations are sufficient to characterize optimal values n[k][/]
for this instance.

Transcribed Image Text:

3 8 1 2 4 3 4 6