Page 40 - 4336

4 ААЛГОРРИТМИ ПОШУУКУ ШЛЛЯХІВ

4.1 Нормаллізованиий графф, вага шшляху

Інооді дугам граффа e ппризначуують діййсні чиисла с , які
i
i
називаюються знначенням вартоості. Чиисло с описує,, наскілльки
i
важко ппройти ддугу із ооднієї веершини в іншу, також ййого можна

інтерпрретувати у сенссі грошо ової варртості, або роззглядатии як

геометрричну довжинуу, час перехооду тоощо. УУ кожнному

конкреттному ввипадку вибираєється сааме те ттлумачеення с , яке
i
ближче підходдить доо змістуу конкрретної задачі. У певвних

практиччних заддачах моожуть вииникати від'ємніі значенння вартоості:

для приикладу, ттранспорртний заасіб, що рухається із однного пуннкту

в іншийй, витраччає чи ззаробляєє під часс цього ггроші; ттож грошшові

витратии можна вважаати доддатною вартісттю, а пприбутокк –

від'ємноою.

Дууги граффа e , якиим признначені ддійсні чиисла с нназиваютться
i
i
зваженими.

Грраф G, щщо описсується трійкоюю виглядду G=(VV, E, С), де

С={с }, i=1, 2, 33, ..., m –– множиина хараактеристик дуг, н називаєтться
i
нормаліізованимм графоом або графомм зі звваженимми дугаами.

Приклаад такогоо графа ннаведениий на риис. 4.1.

Рисунокк 4.1 – ННормалізоований гграф

40