40 ак.ч.
Алгоритм Дейкстра
Входная информация
- Узлы
- Связи направленные
- Место отравления
- Пункт назначения
- Критерии остановки
- Критерии выбора
Порядок действий
- Определение существования входящих связей в пункт назначения
- Определение своего места положения
- Определение узлов, в которые мы можем перейти из текущего
- Определение существования среди соседних узлов пункта назначения
- Если среди соседних узлов находится пункт назначения, то принять его как единственный вариант выбора для следующего перехода.
- Определение количество исходящих связей у найденных узлов
- Исключение узлов с отсутствующими исходящими связями
- Исключение узлов у которых единственная исходящая связь идет в пункт отправления
- Выбор узла с максимальным количеством исходящих связей, при условии, что он отсутсвует в списке посещенных узлов
- Если соседний узел один, то не проверять его на факт посещения
- Отметка текущего узла как посещенного
- Передача информации в общий источник данных
- Переход в выбранный узел
- Переход в пункт 2
Тестовая карта
Домашнее задание
- Основываясь на файле yEd привести запись узлов к виду <point id=”p1″ x=”…” y=”…”/>
- Вспомнить методы и функции работы в Python с массивами (списки и словари)
- Вспомнить Tkinter