There are n galaxies connected by m intergalactic teleport-ways. Each
teleport-way joins two galaxies and can be traversed in both directions.
However, the company that runs the teleport-ways has established an
extremely lucrative cost structure: Anyone can teleport further from their
home galaxy at no cost whatsoever, but teleporting toward their home galaxy
is prohibitively expensive.
Judy has decided to take a sabbatical tour of the universe by visiting as
many galaxies as possible, starting at her home galaxy. To save on travel
expenses, she wants to teleport away from her home galaxy at every step,
except for the very last teleport home.
(a) Describe and analyze an algorithm to compute the maximum number of
galaxies that Judy can visit. Your input consists of an undirected graph G
with n vertices and m edges describing the teleport-way network, an
integer 1 <= s <= n identifying Judy’s home galaxy, and an array D[1 .. n]
containing the distances of each galaxy from s
Comments
Leave a comment