Деревья. Задачи о кратчайших расстояний на графах

Задачи о кратчайших расстояниях на графах.

Пример прикладной задачи:

Задача 1: найти кратчайшее остовное дерево(минимальный покрывающий остов) взвешенного графа.

Алгоритм Прима

Алгоритм КРУСКАла

Проблема Штейнера.

Пример прикладной задачи:

Задача 2: найти один из путей минимальной суммарной длины между двумя заданными вершинами взвешенного орграфа с

Алгоритм Дейкстры (в случае неотрицательных весов ребер.)

Пример прикладной задачи:

Алгоритм Флойда - УОРШАЛЛА.

Пример: Построить матрицу кратчайших расстояний, используя алгоритм Флойда

Фиксируем в качестве ведущих первую строку и первый столбец D0. Остальные элементы матрицы проверяем на возможность выполнения

В матрице S1 эти же клетки заменяем на 1 (первый столбец является ведущим)

Фиксируем в качестве ведущих вторую строку и второй столбец D1. Треугольный оператор выполняется для клеток (1,4) и (4,1).

В матрице S2 эти же клетки заменяем на 2 (второй столбец является ведущим)

Фиксируем в качестве ведущих третью строку и третий столбец D2. Треугольный оператор выполняется для клеток (1,5) и (2,5).

В матрице S3 эти же клетки заменяем на 3 (третий столбец является ведущим)

Фиксируем в качестве ведущих четвертую строку и четвертый столбец D3. Треугольный оператор выполняется для клеток (1,5), (2,5),

В матрице S4 эти же клетки заменяем на 4 (четвертый столбец является ведущим)

Фиксируем в качестве ведущих пятую строку и пятый столбец D4. Треугольный оператор не выполняется нигде.

В матрице S5 соответственно тоже никаких изменений не происходит.

Деревья. Задачи о кратчайших расстояний на графах

Задачи о кратчайших расстояниях на графах.

Пример прикладной задачи:

Задача 1: найти кратчайшее остовное дерево(минимальный покрывающий остов) взвешенного графа.

Алгоритм Прима

Алгоритм КРУСКАла

Проблема Штейнера.

Пример прикладной задачи:

Задача 2: найти один из путей минимальной суммарной длины между двумя заданными вершинами взвешенного орграфа с

Алгоритм Дейкстры (в случае неотрицательных весов ребер.)

Пример прикладной задачи:

Алгоритм Флойда - УОРШАЛЛА.

Пример: Построить матрицу кратчайших расстояний, используя алгоритм Флойда

Фиксируем в качестве ведущих первую строку и первый столбец D0. Остальные элементы матрицы проверяем на возможность выполнения

В матрице S1 эти же клетки заменяем на 1 (первый столбец является ведущим)

Фиксируем в качестве ведущих вторую строку и второй столбец D1. Треугольный оператор выполняется для клеток (1,4) и (4,1).

В матрице S2 эти же клетки заменяем на 2 (второй столбец является ведущим)

Фиксируем в качестве ведущих третью строку и третий столбец D2. Треугольный оператор выполняется для клеток (1,5) и (2,5).

В матрице S3 эти же клетки заменяем на 3 (третий столбец является ведущим)

Фиксируем в качестве ведущих четвертую строку и четвертый столбец D3. Треугольный оператор выполняется для клеток (1,5), (2,5),

В матрице S4 эти же клетки заменяем на 4 (четвертый столбец является ведущим)

Фиксируем в качестве ведущих пятую строку и пятый столбец D4. Треугольный оператор не выполняется нигде.

В матрице S5 соответственно тоже никаких изменений не происходит.

2.02M

Категория:

Информатика

Информатика

Похожие презентации:

Граф. Деревья. Задачи о кратчайших расстояний на графах

Задачи на графы

Задачи на графы

Занимательные задачи. Задачи со словами

Занимательные задачи. Задачи со словами

Шахматные задачи. Задачи на сложные условия

Шахматные задачи. Задачи на сложные условия

Занимательные задачи информатики. Задачи о лжецах

Занимательные задачи информатики. Задачи о лжецах

Задачи по информатике

Задачи по информатике

Комбинаторные задачи

Комбинаторные задачи

Деревья. Задачи о кратчайших расстояний на графах

1. Деревья. Задачи о кратчайших расстояний на графах

ДЕРЕВЬЯ.
ЗАДАЧИ
О
РАССТОЯНИЙ НА ГРАФАХ
КРАТЧАЙШИХ

2.

ДЕРЕВЬЯ
Связный граф

English Русский Правила