=top>
(5, 6)
8
(6, 7)
3
В
2.
Побудова мінімального кістяка.
Мінімальна кістяк - це остовное дерево графа, що має мінімальний можливий вага, де під вагою дерева розуміється сума ваг входять до нього ребер. <В
Крок 0 : C 0 = Г?, = {1, 2, 3, 4, 5, 6, 7}
В В В В В В В В
Крок 1 : C 1 = {1}, = {2, 3, 4, 5, 6, 7}
В В В
Крок 2 : min l (1-2) = 5, j * = {2}, C 2 = {1, 2}, = {3, 4, 5, 6, 7}
Крок 3 : min l (2-3) = 4, j * = {3}, C 3 = {1, 2, 3}, = {4, 5, 6, 7}
В В В В В В В В В В
Крок 4 : min l (3-4) = 2, j * = {4}, C 4 = {1, 2, 3, 4}, = {5, 6, 7}
В В В В В В В В В
Крок 5 : min l (4-5) = 3, j * = {5}, C 5 = {1, 2, 3, 4, 5}, = {6, 7}
В В В В В В В
Крок 6 : min l (5-6) = 8, j * = {6}, C 6 = {1, 2, 3, 4, 5, 6}, = {7}
В В В В В В В В В В
Крок 7 : min l (6-7) = 3, j * = {7}, C 7 = {1, 2, 3, 4, 5, 6, 7}, = Г?
В В В В В В В В В
Мінімальна кістяк буде виглядати наступним чином:
В В
В В
Сума ваг ребер кістяка дорівнює 5 +4 +2 +3 +8 +3 = 25 од.
Приклад:
Необхідно з'єднати населені пункти під номерами 1 - 7 автомобільними дорогами, при умови, що їх протяжність буде мінімальна. p> Відстані вказані поруч з кожним ребром мережі. p> Побудова мінімального кістяка вирішує це завдання. p> При цьому протяжність автомобільних доріг, що з'єднують всі населені пункти, буде дорівнює 25 кілометрам. p> 3.
Знаходження найкоротшого маршруту.
Знаходження найкоротшого маршруту полягає в з'єднанні джерела (1) зі стоком (7) мінімальним відстанню.
Крок 1: Початкова точка {1}.
Знаходимо найкоротший маршрут до наступної точки.
В В В В В В В В В В
Крок 2: Точки {1} і {2} з'єднуємо найкоротшим маршрутом з наступного крапкою.
В В В В В В В В В
Крок 3: Точки {1} і {3} з'єднуємо найкоротшим маршрутом з наступного крапкою.
В В В В В В В В В
В результаті отримуємо два альтернативних шляхи - один з них позначений пунктиром.
В
Крок 4: Крапку {4} з'єднуємо найкоротшим маршрутом з наступного крапкою.
В В В В В В В В В
Крок 5: Точки {4} і {5} з'єднуємо найкоротшим маршрутом з наступного крапкою.
В В В В В В В В В В В В
Крок 6: Точки {4} і {6} з'єднуємо найкоротшим маршрутом з наступного крапкою.
В В В В В В В В В
У результаті ітерацій ми знайшли найкоротші маршрути, з...
