Пути в графах

Четверг, 25 октября 2012
ФМЛ 239, Актовый зал

Описание

Нахождение кратчайших путей из одной вершины в невзвешенных графах, поиск в ширину (визуализация). Нахождение кратчайших путей из одной вершины в графах с положительными весами, алгоритм Дейкстры (визуализация), оценка времени работы при различных реализациях очереди с приоритетами (массивом, двоичной кучей, d-чной кучей). Нахождение кратчайших путей из одной вершины в графах, в которых есть рёбра отрицательного веса, алгоритм Беллмана-Форда, проверка наличия цикла отрицательного веса.