40 ак.ч.

Алгоритм Дейкстра 

Входная информация 

  1. Узлы
  1. Связи направленные 
  1. Место отравления 
  1. Пункт назначения 
  1. Критерии остановки 
  1. Критерии выбора 

Порядок действий 

  1. Определение существования входящих связей в пункт назначения 
  1. Определение своего места положения 
  1. Определение узлов, в которые мы можем перейти из текущего 
  1. Определение существования среди соседних узлов пункта назначения 
  1. Если среди соседних узлов находится пункт назначения, то принять его как единственный вариант выбора для следующего перехода. 
  1. Определение количество исходящих связей у найденных узлов 
  1. Исключение узлов с отсутствующими исходящими связями 
  1. Исключение узлов у которых единственная исходящая связь идет в пункт отправления 
  1. Выбор узла с максимальным количеством исходящих связей, при условии, что он отсутсвует в списке посещенных узлов 
  1. Если соседний узел один, то не проверять его на факт посещения 
  1. Отметка текущего узла как посещенного 
  1. Передача информации в общий источник данных 
  1. Переход в выбранный узел 
  1. Переход в пункт 2 

Тестовая карта

Карта в формате yEd

Домашнее задание

  1. Основываясь на файле yEd привести запись узлов к виду <point id=”p1″ x=”…” y=”…”/>
  2. Вспомнить методы и функции работы в Python с массивами (списки и словари)
  3. Вспомнить Tkinter