, 4 = 0, 3,5 = 3, 3,4 = 5.
В
Рисунок 4 - Змінена мережу після виконання третин ітерації
Ітерація 4. Позначаємо вершину 4 m4 = 2 (малюнок 5). Подальша позначка неможлива, тому переходимо до етапу 2. Суміжними з раніше позначеними вершинами є вершини 5,6. З чого визначаємо? = Min { 2,5, 3,5, 4,5, 4,6} = 3 і після перетворення маємо 2,5 = 5, 3 , 5 = 0, 4,5 = 0, 4,6 = 5.
В
Рисунок 5 - Змінена мережу після виконання четвертої ітерації
Ітерація 5. У вершину 5 ведуть дуги нульової довжини як з вершини 3, так і з вершини 4. Керуючись тими ж міркуваннями, що і на ітерації 3, пометим вершину 5 числом m5 = 3 (малюнок 6). Подальша позначка неможлива, тому переходимо до етапу 2. Суміжній з раніше зазначеними вершинами є вершина 6. З чого визначаємо? = Min { 4,6, 5,6} = 2 і після перетворення маємо 4 , 6 = 3, 5,6 = 0.
В
Малюнок 6 - Змінена мережу після виконання п'ятої ітерації
Ітерація 6. У вершину 6 веде дуга нульової довжини з вершини 5, тому помічаємо її числом m6 = 5 (малюнок 7). Оскільки ми відзначили кінцеву вершину маршруту, то алгоритм завершено і ми можемо, використовуючи значення відміток для батьків, виписати шуканий найкоротший шлях (1, 3, 5, 6). <В
Малюнок 7 - Змінена мережу після виконання шостий ітерації
Слід також додати, що якби наш вибір на ітераціях 3 та 5 був іншим, то ми отримали б альтернативний шлях тієї ж довжини (1, 2, 4, 5, 6), тобто розглянута задача має кілька рішень.
3. Програмне забезпечення
.1 Обгрунтування вибору середовища розробки
При вирішенні поставленого завдання оптимально використовувати для подання інформаційних матеріалів мову Delphi, яка є мовою високого рівня і дозволяє швидко і ефективно створювати додатки.
Для реалізації методу Мінті була обрана система програмування Delphi версії 7 фірми Borland, так як вона надає найбільш широкі можливості для програмування додатків ОС Windows. - це продукт Borland International для швидкого створення додатків. Високопродуктивний інструмент візуального побудови додатків включає в себе справжній компілятор коду і надає засоби візуального програмування, кілька схожі на ті, що можна виявити в Microsoft Visual Basic або в інших інструментах візуального проектування. В основі Delphi леж...