6. A farmer wishes to transport a truckload of eggs from one city to another city through a given road network. The truck will incur a certain amount of breakage on each road segment; let ij denote the fraction of the eggs broken if the truck traverses the road segment (i; j). Give an algorithm to nd a route minimizing the total breakage in O n 2 time where n is the total number of cities in the road network. You are not allowed to take logarithms because they yield irrational data.