Лекция 10. Кратчайшие пути (продолжение)

Алгоритм Дейкстры. Аксиоматика длины путей, примеры: аддитивная (неотр. веса), максимум. Пометки (W/G/B) вершин, их смысл. Инициализация. Идея: перекрашиваем серую вершину с мин. оценкой в чёрный. Просмотр вершины (функция Scan). Псевдокод алгоритма. Доказательство: обоснование перекрашивания G->B от противного. Время работы (аддитивная функция длины): O(V^2). Хранение серых вершин в куче. Бинарная куча O(E log V), k-ичная куча O(E log V / log(E/V)), фиббоначиева куча O(E + V log V). Восстановление пути, сохранение предка, дерево кратчайших путей.