Подумал, что если так получилось, что в графе много мостов и средний размер
двуссвязной компоненты небольшой, например, порядка логарифма от числа вершин, то можно намного эффективнее запустить Дейсктру:
1. Найти все
мосты - O(n)
2. Запустить дейкстру от каждой двусвязной компоненты:
всего компонент: n/logn
обработка одной компоненты: log^2(n) или logn * log(logn)). на практике конечно для таких маленьких подгарфов использовать массив за log^2(n) вместо кучи за logn * log(logn))
итого: n/logn * log^2(n) = n * logn для массива (но тут с очень маленькой константой) или n/logn * logn * log(logn)) = n * log(logn) асимптотически лучше, но на практике должно быть лучше с массивом за log^2 на обработку компоненты
3. Затем просто O(n) пересчитать расстояния от S до всех по формуле: D(s, vi) + d(vi, vj) как префикс расстояния, думаю из картинки будет понятно
Подумал, что такое не так и редко встречается, например, в сетевом роутинге вроде бы именно такая картика, где много мостов и размер компонент двусвязности мал
