Napoleon Bonaparte, the great French Emperor and ruthless military genius1 seeks to
establish efficient administrative communication between Paris and N other provinces
in France through one-way broadcast messages from Paris along pre-specified paths.
There are K different languages spoken across the French empire, and thus a lot of
consecutive translations may need to happen along the way to a remote province when
a message is sent, causing unwanted delays. Each province speaks just one of K
languages. Napoleon’s messengers carry message scrolls from Paris (in French) along
a graph G = (V,E) of roads and sailing routes. All roads lead to Paris and only
three-way intersections are present. At each intersection, lies a checkpost where scrolls
come and the message is translated to the language required of the next node in the
path. The emperor has a K × K matrix, C, of positive numbers for the cost C(i, j)
of translating from language i to language j. The translation costs in the matrix are
optimal for each pair and are not symmetric.
(a) Design the efficient algorithm that is in Napoleon’s mind (Assume that you can
read the mind of the genius) to select the language of the scrolls to be used on
each segment (and the translations done at each checkpost) in order to minimize
the total cost of the translations.
(b) Analyze the running time and space requirements of Napoleon’s algorithm and
prove correctness.