Инд работа4(алг фр волны)

Индивидуальная работа №4

Нахождение минимального пути в орграфе. Алгоритм фронта волны.

Для выполнения и защиты индивидуальной работы №4 необходимо изучить теоретический материал по данной теме.

Перечень основных вопросов по четвертой индивидуальной работе:

1. Определения пути (маршрута) в орграфе (графе), длины пути (маршрута), количества путей (маршрутов).

2. Понятия образа, прообраза вершины и множества вершин.

3. Алгоритм фронта волны для нахождения минимального пути в орграфе (понятие фронта волны k-ого уровня, формулы для нахождения фронта волны k-ого уровня, формулы для определения вершин, входящих в искомый путь, условия отсутствия пути, определение количества минимальных путей по найденным фронтам волны)

1. Используя алгоритм фронта волны, найти минимальный путь из v₁ в v₅ в орграфах, заданных матрицами смежности. Построить графы.

I II III IV V

VI VII VIII IX X

2. Найти все кратчайшие пути из вершины v₁ во все остальные вершины. Построить графы.

I II III

IV V VI

VII VIII IX X