Typically, when we use Dijkstra’s algorithm to find the lightestpath from node s to nodes t in the directional G, then the weightof the road is defined as the combined weight of the edges formingit. Now we want to change that definition and find that way from sto t where the heaviest edge in the road is lightest. Then thelength of the road does not matter, but just how heavy the heaviestedge in it is. Show an algorithm that solves this task with thesame time complexity as Dijkstra’s algorithm. Explain and justifythe algorithm.
Solution