20 декабря 2008. Алгоритм Дейкстры
17 января 2009. Алгоритм Флойда
31 января 2009. Алгоритм Форда-Белмана
7 февраля 2009. Восстановление пути
7 февраля 2009. Деревья - знакомство
Список вопросов к зачету
- Способы представления графов: матрица смежности, список ребер и граф, заданный неявно
- Алгоритм Дейкстры
- Алгоритм Форда-Белмана
- Алгоритм Флойда
- Дополнительные вопросы по алгоритмам поиска кратчайших путей:
- Область применения каждого алгоритма и решаемая им задача.
- Обоснование каждого алгоритма.
- С каким спобом представления графа (матрица смежности, список ребер) данный алгоритм работает
- Что такое "бесконечность", как и зачем ей пользуются
- Оценка сложности (числа выполняемых операций) алгоритма*
- Восстановление кратчайшего пути по вычисленным длинам путей
- Определение дерева. Свойства деревьев
- Построение минимального каркаса (уметь это делать на листочке)
Факультатив