Дейкстра почти за линейное время (для неориентированного графа)?

Question

[floppa322]

Подумал, что если так получилось, что в графе много мостов и средний размер двуссвязной компоненты небольшой, например, порядка логарифма от числа вершин, то можно намного эффективнее запустить Дейсктру:

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) как префикс расстояния, думаю из картинки будет понятно


Подумал, что такое не так и редко встречается, например, в сетевом роутинге вроде бы именно такая картика, где много мостов и размер компонент двусвязности мал

Answer 1

[Wataru]

В сетевом роутинге, в основном, нет* центрального узла с информацией о всей топологии, чтобы искать пути. Так что там вообще не работает Дейкстра, а работают распределенные алгоритмы.

А так, да, на очень специфичных гарфах всеядный алгоритм Дейкстры не самый лучший вариант. И ваш алгоритм тут получается быстрее.

* Вообще, есть такая тема, как Software Defined Networking, где как раз есть центральный узел, который все и решает, но это чисто теория пока, и там суть не в поиске кратчайших путей в графе а во всяких сложных механизмах приоритезации трафика и устойчивости к сбоям.

Comments

[floppa322]

Похоже, что с алгоритмами на графах примерно такая же проблема как и в сортировках, нужно определить паттерн данных - пример