gn="justify"> безліч вершин, U безліч дуг, з визначеної на ній функцією вартості сіj ((і, j) дуга з U), для фіксованих i1 і is знайти шлях
= ((i1, i2), (i2, i3) ..., (is-1, is))
з вершини i1 у вершину is, довжина якого
В
найменша.
1.2 Опис методу Мінті
Метод Мінті рішення задачі про найкоротший шлях в мережі являє собою ітеративний процес, в ході якого будується шлях L = (s = i0, i1, ..., ip-1, ip = t).
На попередньому (нульовому) етапі алгоритму:
В· формується масив значень так званих модифікованих довжин i, j, які перед початком першої ітерації покладаються рівними сi, j ? 0;
В· здійснюється відмітка вершини i0 = s числом mi0 = 0.
Стандартна ітерація включає етапи:
. Відмітка вершин мережі. Позначимо безліч вершин cети, відмічених на попередніх ітераціях, як (на першій ітерації = {i0}). Для кожної вершини i ? шукаються дуги, що з'єднують її з ще не позначеними вершинами-нащадками j, модифікована довжина яких i, j = 0. Знайдені таким способом вершини j позначаються числом mj = i, що вказує на В«батькаВ». У тому випадку, коли відразу кілька дуг, що мають i, j = 0, закінчуються в одній і тій же вершині j, значення для її позначки вибирається довільно.
Якщо серед знову помічених вершин виявиться вершина t, то, значить, знайдений шуканий шлях (i0, i1, ..., i (p-1), ip), де на чому алгоритм завершується.
У разі, якщо вершини t немає серед відзначених, і одночасно не можна відзначити жодної нової вершини, то переходимо до етапу 2.
. Перетворення значень модифікованих довжин дуг. Для кожної вершини i ? шукаються дуги, що з'єднують її з ще не позначеними вершинами j, і знаходяться Далі модифіковані довжини всіх дуг, які з'єднують відмічені вершини з невідзначеними (i ? , j ? ), зменшуються на величину в результаті чого найкоротші невикористані дуги отримують нульову модифіковану довжину.
Потім відбувається перехід до наступної ітерації. p align="justify"> Шлях, побудований за методом Мінті, буде найкоротшим. Це можна довести за допомогою індукції за номером ітерації, на якій була позначена вершина t, а...
