Содержание
- 2. Поиск путей (маршрутов) с минимальным числом дуг (ребер) Путь (маршрут) в орграфе D (графе G) из
- 3. Алгоритм фронта волны ( нахождения минимального пути в орграфе D) Рассмотрим орграф D = (V, X),
- 4. Шаг 1. Помечаем v индексом 0. Помечаем вершину, принадлежащую образу v индексом 1, множество вершин с
- 5. Шаг 3. IF w ∉ FWk(v), THEN переход к шагу 4. ELSE, существует путь из v
- 6. Шаг 4. 1) Помечаем индексом (k+1) все непомеченные вершины, которые принадлежат образу множества вершин с индексом
- 7. Замечания Множество FWk(v) в алгоритме называется фронтом волны k-го уровня. Вершины w1 w2 … wk-1 могут
- 8. Пример Найти минимальный путь из v1 в v6 в орграфе D, заданном матрицей смежности A.
- 10. Прямой ход алгоритма. Определение фронтов волны. FW1(v1)={v4,v5}; v6 ∉ FW1(v1) FW2(v1)=D(FW1(v1))\{v1,v4,v5}= ={v1,v2,v3,v4,v5} \{v1,v4,v5}= ={v2,v3}; v6 ∉
- 11. Обратный ход алгоритма. Нахождение вершин минимального пути. Нахождение вершин ведется от последней к первой. FW2 (v1)
- 13. Скачать презентацию