Структура данных для кратчайших путей

Пусть $G$ - невзвешенный неориентированный граф с $n$ вершинами и $m$ ребрами. Можно ли предварительно обработать $G$ и создать структуру данных размером $m \cdot \mathrm{polylog}(n)$ чтобы он мог отвечать на запросы вида «расстояние между $u$ и $v$ » за время O (n)?

Проблема кажется слишком простой, чтобы быть нерешенной.

Это очень интересный вопрос. На высоком уровне вы спрашиваете, можно ли предварительно обработать граф таким образом, чтобы запросы по кратчайшему пути стали независимыми от плотности графа, без использования большого дополнительного пространства - интересно, но, как вы говорите, не решено.

Если вы довольны приблизительными расстояниями, вот способ получить приближение. Пусть G - взвешенный неориентированный граф с n узлами и m ребрами. В следующей статье показано, что для приближенных дистанционных запросов проектирование структур данных для графов с m ребрами не сложнее, чем для графов, в которых каждый узел имеет степень, ограниченную m / n :$2$$G$$n$$m$$m$$m/n$

Р. Агарвал, П. Б. Годфри, С. Хар-Пелед, Приближенные дистанционные запросы и компактная маршрутизация в разреженных графах, INFOCOM 2011

Итак, предположим, что - ограниченный граф с m / n- степенью. Выборка α = O ( m / n ) узлов равномерно случайным образом; Назовите эти ориентиры. Во время фазы предварительной обработки сохраняйте расстояние от каждого узла ориентира до каждого другого узла на графике; это требует O ( м ) пространства. Для каждого узла u сохраните его ближайший ориентир ℓ ( u ) . Кроме того, храните график в структуре данных, скажем, как список смежности.$G$$m/n$$\alpha = O(m/n)$$O(m)$$u$$\ell(u)$

Когда запрашивается расстояние между и v , растут шары вокруг обоих узлов - шар узла w определяется как набор узлов, которые строго ближе к w, чем к его ближайшему ориентиру, например, ℓ ( w ) . Можно ожидать, что размер каждого шарика O ( n 2 / m ) , в ожидании. Пусть Γ ( u ) = B ( u ) ∪ N ( B ( u ) ) , где B ( $u$$v$$w$$w$$\ell(w)$$O(n^2/m)$$\Gamma(u) = B(u) \cup N(B(u))$ - шар узла u, а N ( B ( u ) ) - множество соседей узлов в B ( u ) . Можноожидать,что размер Γ ( u ) равен O ( n ) в ожидании.$B(u)$$u$$N(B(u))$$B(u)$$\Gamma(u)$$O(n)$

Отвечая на вопрос: если , вернуть min x ∈ Γ ( u ) ∩ Γ ( v ) { d ( u , x ) + d ( v , x ) } ; иначе, если d ( u , ℓ ( u ) ) ≤ d ( v , ℓ ( $\Gamma(u) \cap \Gamma(v) \neq \emptyset$$\min_{x \in \Gamma(u) \cap \Gamma(v)} \{d(u, x) + d(v, x)\}$ , вернуть d ( u , ℓ ( u ) ) + d ( ℓ ( u ) , v ) ; иначе вернуть d ( v , ℓ ( v ) ) + d ( ℓ ( v ) , u ) . Нетрудно показать, что это 2- приближение.$d(u, \ell(u)) \leq d(v, \ell(v))$$d(u, \ell(u)) + d(\ell(u), v)$$d(v, \ell(v)) + d(\ell(v), u)$$2$

С точки зрения времени запроса, обратите внимание, что растущим шарам требуется времени для графа с m / n- градусной степенью ; построение Γ ( u ) и Γ ( v ) с учетом соответствующих шаров занимает O ( n ) времени (поскольку в структуре данных хранятся соседи); и проверка того, является ли Γ ( u ) ∩ Γ ( v ) пустой или нет, также занимает O ( n ) время.$O(n)$$m/n$$\Gamma(u)$$\Gamma(v)$$O(n)$$\Gamma(u) \cap \Gamma(v)$$O(n)$

Вышеуказанные границы находятся в ожидании; Я думаю, что это легко дерандомизировать конструкцию. К сожалению, этот метод не позволяет получить приближение лучше, чем . Это очень интересный вопрос, хотя ....$2$

То, что вам нужно, называется «оракул расстояния». К сожалению, я не очень знаком с дистанционными оракулами, поэтому могу только отослать вас к основополагающему документу благодаря Торупу и Цвику:

Миккель Торуп и Ури Цвик. Приблизительное расстояние оракулов. STOC '01, 2001.

Вот выдержка из аннотации:

Пусть - неориентированный взвешенный граф с | V | = n и | E | = М . Пусть k будет целым числом. Мы показываем, что G = ( V , E ) можно предварительно обработать за ожидаемое время O ( k m n 1 / k ) , построив структуру данных размером O ( k n 1 + 1 /$G = (V, E)$$|V| = n$$|E| = m$$k$$G = (V, E)$$O(kmn^{1/k})$ , так что на любой последующий дистанционный запрос можно ответить примерно за O ( k ) время. Приблизительное возвращаемое расстояние имеет растяжение не более 2 k - 1 , т. Е. Частное, полученное путем деления расчетного расстояния на фактическое расстояние, лежит между 1 и 2 k - 1 . [...] Требуемое пространство нашего алгоритма является [...] по существу оптимальным.$O(kn^{1+1/k})$$O(k)$$2k - 1$$2k - 1$

Согласно их результатам, то, что вы запрашиваете, в основном выполнимо даже для взвешенных графиков: выбор дает оракула размера O ( n 2 ), полученного в ожидаемое время O ( m n ) , который может ответить на ваши запросы кратчайшего пути с 1 - растянуть в O ( 1 ) раз!$k=1$$O(n^2)$$O(mn)$$1$$O(1)$

Дистанция оракулов - это очень хорошо изученная область, так что я думаю, вы сможете копать дальше.