Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечении строк и столбцов таблиц, обозначают стоимость перевозок между соответствующими соседними станциями. Если пересечение столбца и строки пусто, то станции не являются соседними. Стоимость перевозки по маршруту складывается из стоимостей перевозок между соседними станциями. Перевозки между населенными пунктами A, B, C, D, E осуществляют 3 компании, представившие стоимость своих услуг в табличной форме. Какая компания обеспечивает минимальную стоимость проезда из А в В?
Решение: Построим графы, отражающие стоимость перевозок каждой компании.
Компания 1.
Из пункта А в пункт В мы можем попасть 2 путями:
А→С→В = 3+4=7
А→С→Е→В=3+2+2=7
Компания 2.
Из пункта А в пункт В мы можем попасть 2 путями:
А→С→В = 3+4=7
А→Е→С→В=1+2+4=7
Компания 3.
Из пункта А в пункт В мы можем попасть 4 путями:
А→С→В = 3+4=7
А→Е→С→В=4+2+4=10
А→С→Е→В=3+2+2=7
А→Е→В = 4+2=6
Самым минимальным по стоимости оказался проезд у компании 3. Если ехать по маршруту А→Е→В, то цена поездки составит 6, в остальных случаях 7 или 10.
Ответ: компания 3.