ів пам'яті, необхідний для представлення графа за допомогою списків інцидентності, буде, очевидно, мати порядок m + n .
2.2.2 Алгоритми пошуку найкоротшого шляху
Шлях між двома вершинами називається найкоротшим, якщо його вартість мінімальна серед вартостей всіх можливих шляхів між цими двома вершинами. Між парою вершин, очевидно, може бути декілька найкоротших шляхів однакової вартості. Найкоротшого шляху між двома вершинами може не існувати у випадках, коли вони лежать у різних компонентах.
Існує багато різних алгоритмів, в основі яких лежить систематичний перебір вершин графа.
Пошук в ширину
Основна ідея пошуку в ширину - у вершини i проглядаються і поміщаються в чергу відразу всі її нові «сусіди», після чого i стає використаної і віддаляється з черги.
Так як ми знаходимо відразу всіх сусідів, пошук, як хвиля від джерела, рівномірно поширюється в усі сторони. Тому, в черзі, спочатку знаходяться всі вершини, віддалені від початкової вершини на відстань одного ребра, через деякий час - всі вершини, віддалені на відстань двох ребер і т.д. Якщо довжини ребер не задані, то шлях, знайдений таким чином, буде найкоротшою.
Недоліком даного алгоритму є те, що пошук йде рівномірно у всіх напрямках, замість того, щоб бути спрямованим у бік цілі.
Алгоритм пошуку з поверненням
Опишемо загальну схему алгоритму з поверненням, що дозволяє значно скоротити число кроків в алгоритмах повного перебору всіх можливостей. Щоб застосувати цей метод, шукане рішення має мати вигляд послідовності ( x1, x2,., Xn).
Основна ідея алгоритму полягає в тому, що ми будуємо рішення, починаючи з порожньою послідовності довжини 0. Маючи часткове вирішення ( x1, x2,., xi), ми намагаємося знайти таке допустиме значення xi +1 , щодо якого ми не можемо відразу укласти, що ( x1, x2,., xi + 1) не можна розширити до повного вирішення (або ( x1, x2,., xi +1) вже є рішенням). Якщо таке передбачуване, але ще не використане рішення xi +1 існує, то ми додаємо його до нашого частковому вирішенню і продовжуємо процес для послідовності ( x1, x2,., xi +1). Якщо його не існує, то ми повертаємося до нашого частковому вирішенню ( x1, x2,., xi - 1) і продовжуємо наш процес, відшукуючи нове, ще не використане допустиме значення xi - звідси назва «алгоритм з поверненням».
Ми припускаємо також, що існує деяка проста функція, яка безпідставного частковому вирішенню ( x1, x2,., xi) ставить у відповідність значення P (x1, x2,., xi) ( істина або брехня) таким чином, що якщо P (x1, x2,., xi)=брехня , то послідовність ( x1, x2,., xi) не можна розширити до рішення.
Якщо P (x1, x2,., xi)=істина , то ми говоримо, що значення xi припустимо (для часткового вирішення ( x1, x2,., xi - 1)) , ал...
