Ответ:

Сравним самые дешёвые маршруты из A в B для каждой компании. Стоимость маршрута равна сумме стоимостей его участков.

  1. Компания 1. Маршрут A–C–B стоит 3 + 4 = 7. Маршрут A–C–E–B также стоит 3 + 2 + 2 = 7. Стоимость перевозки — 7.
  2. Компания 2. Маршрут A–C–B стоит 3 + 4 = 7. Маршрут A–E–C–B также стоит 1 + 2 + 4 = 7. Стоимость перевозки — 7.
  3. Компания 3. Маршрут A–E–B стоит 4 + 2 = 6. Маршрут A–C–B стоит 3 + 4 = 7, поэтому маршрут через E дешевле. Стоимость перевозки — 6.
КомпанияСамый дешёвый маршрутСтоимость
1A–C–B или A–C–E–B7
2A–C–B или A–E–C–B7
3A–E–B6

Ответ: компания 3; минимальная стоимость перевозки из A в B равна 6.