Кратчайшие расстояния в графах

1. [10 минут] Классификация задач поиска пути
1. Невзвешенный граф: bfs, O(E), 1950.
2. Граф без отрицательных рёбер: Дейкстра за O(n²), O(mlogn), O(m + nlogn), O(m + nlogC), O(m + nsqrtlogC)
3. На самом деле еще умеют для неорграфов искать путь за O(n + m), и для орграфов за O(m + nloglogmin(n,C))
4. Отрицательные рёбра, отрицательные циклы, алгоритма для минимального простого пути не существует
5. Граф с отрицательными весами рёбер
1. 58' Ford,Bellman − O(EV)
2. 83' Gabow − O(EV^3/4log(nU))
3. 89' Gabow,Tarjan − O(EV^1/2log(nU))
4. 93' Goldberg − O(EV^1/2logN)
2. [35 минут] Невзвешенный граф
1. [15 минут] bfs (алгоритм без очереди, алгоритм с очередью, восстановление пути и сравнение с dfs, граф кратчайших путей, куда идут рёбра, код!)
2. [5 минут] матрица расстояний и транзитивное замыкание за O(VE)
3. [15 минут] транзитивное замыкание за O(VE/w) (bitset, конденсация, динамика)

1. [25 минут] Модификации bfs для взвешенного графа без отрицательных рёбер
1. Аналог bfs (позже докажем, что он за O(VE) работает)
2. 0-1-bfs
3. 1-k-bfs (на k+1 очереди, с раскатерением рёбер)
2. [25 минут] Дейкстра
1. Дейкстра за V*ExtractMin + E*DecreaseKey (V², ElogV, E + VlogV, Elog_E/VV)
2. Алгоритм A^*
3. Реклама: алгоритм Гольдберга для поиска путей