Алгоритмы решения задач на сетях
Алгоритм нахождения минимального остовного дерева
Обозначим черезх N множество вершин сети N={1,2,...n}
Ck - множество вершин включенных в остовное дерево на k- ом шаге. 
- оставшиеся вершины.
ШАГ 1. Выбираем любую вершину графа i из множества 
ШАГ 2. В множестве 
выбираем вершину j , которая соединена самой короткой дугой с выбранной начальной вершиной.
ШАГ 3. В множестве выбираем следующую вершину, которая соединена самой короткой дугой с одной из вершин уже отобранных ранее в остовное дерево. При этом не должно образовываться циклов.
Процесс продолжается до включения всех вершин в остовное дерево.
Пример:
Начнем с вершины1. Ребро 1-2 самое короткое, поэтому включаем в остовное дерево вершину 2.
Анализируем длины всех ребер соединяемых (инцидентных_ вершинам 1 и 2. Выбираем вершину 5.
Следующей вершиой выбиаем 4.
Далее 6 вершиа.
Следующая и последняя вершина 3.
Подсчитаем общее растояние: 1+3+4+3+5=16
Дерево будет иметь вид:
Алгоритм нахождения кратчайшего пути
Алгоритм Дейкстры
Рассмотрим работу алгоритма на примере. Найдем кратчайший путь между вешинами 1-7.
Шаг.
Выделяем узел 1. Помечем все узлы связые с 1 метками.
Эти метки (вреенные) указывают на номер узла , связанного с данным узлом. На этом шаге это первый узел. Первая цифра метки указывает расстояние до первого узла.
Ребро, связывающее узел 3 с узлом 1 самое короткое. Поэтому 3 узел помечаем постоянной меткой.
|
|
|
Шаг.
Отбираем все узлы, которые соединяются с 3 одним ребром и не имеют постоянных меток. Это узлы 2, 4,6.
Срниаем маршрты 1-2 и 1-3-2 замечаем, что длина перого 20 меньше второго 25. Следоателно метка узла 2 не меняется (мы не идем от 3 к 2).
Сравниваем маршуты 1-4 и 1-3-4. Последни короче. Поэтому временная метка узла 4 менется на (23,3).
Аналогичные рассуждения для узла 6. Его метка будет (15+30,3)=(45,3)
Ребро соединяющее 2 и 1 самое короткое. Любой маршрут от 1 к узлу 2 будет длиннее. Поэтому узлу 2 приписывается постоянная метка.
Шаг.
Отбраем все узлы, которые соединены с узлом 2 одним ребром и не имеют постоянных меток. Это узел 6.
Узел 5 получает метку (40,2)
Узел 7 получает метку (60,2)
Путь 1-3-4 кратчайший к узлу 4. Поэтому делаем ему постоянную метку.
Шаг.
Отбраем все узлы, которые соединены с узлом 4 одним ребром и не имеют постоянных меток. Это узлы 5 и 7.
Сравниваем маршруты 1-3-6 и 1-3-4-6 Получаем 45 и 43. Второй короче. Меняем узлу 6 метку на (43,4).
Маршрут 1-2-5 кратчайший к узлу 5. Поэтому делаем узлу 5 постоянную метку (40,2).
Следующие шаги приводят к постоянной метке узла 6 (43,4) и (49,5) для узла 7.
Таким образом кратчайший путь 49.
Кратчаий путь отконца 7-5-2-1
|
|
|
Замечание: На каждом шаге временная метка одного из узлов меняется на постоянную по следующему правилу: рассматриваются все узлы с временными метками и выбирается тот из них, длина маршрута которого до1 является минимальной.
Дата добавления: 2018-04-04; просмотров: 605; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!