Алгоритм поиска кратчайших путей для разреженных графов большой размерности | ПДМ. 2013. № 1(19).

Алгоритм поиска кратчайших путей для разреженных графов большой размерности

Рассматривается задача поиска кратчайших путей между всеми вершинами взвешенного ненаправленного разреженного графа. Предлагается алгоритм «разборки и сборки графа», использующий решение задачи на графе малой размерности для получения решения для исходного графа. Приводится сравнение предлагаемого алгоритма с одним из быстрых классических алгоритмов на данных из открытого доступа.

All-pairs shortest paths algorithm for highdimensional sparse graphs.pdf Введение Задача поиска кратчайших путей между всеми парами вершин графа (APSP — All-Pairs Shortest Path problem) является одной их классических в теории графов. Такой её статус обусловлен тем, что при решении оптимизационных задач на графах из многих областей (задача коммивояжёра, транспортная задача и многие другие) необходимо знать расстояния между всеми вершинами графа. Более того, сама задача представляет большой исследовательский интерес, так как её решение позволяет ответить, например, на такие вопросы: — Как попасть из любого пункта А в любой пункт Б с наименьшими затратами времени/денежных средств? — Каков ближайший/самый удалённый пункт для А и каково расстояние до него? Новый приток интереса к задаче произошёл с появлением создаваемых полуавтоматически графов высокой подробности, описывающих структуры реального мира. Подобные графы имеют размерность 106 и более, а их подробность со временем будет только увеличиваться. Поэтому актуальным становится вопрос об ускорении поиска кратчайших путей в графах, обладающих большой размерностью. Для решения задачи APSP существует множество алгоритмов, но нет способа, получающего решения одинаково быстро для любого вида входов. В связи с этим алгоритмы решения APSP принято делить по типу графов, на которых задача решается. Известны алгоритмы, в которых входами являются направленные графы [1], полные графы [2], взвешенные графы [3], невзвешенные графы [4], разреженные графы [5]. В данной работе рассматривается задача APSP для взвешенных ненаправленных разреженных графов большой размерности с неотрицательными весами ребер. Предлагается алгоритм, сводящий решение задачи к замене исходного графа графом меньшей размерности и решению задачи на нём. Приводится сравнение предлагаемого алгоритма с быстрым классическим алгоритмом на графах дорожных сетей. 1. Постановка задачи и определения 1.1. Термины и определения Рассматривается задача поиска кратчайших путей на связном ненаправленном разреженном взвешенном графе G = (V, E,w) с неотрицательными весами рёбер, где V = (vi, v2,..., vn} — множество вершин графа; E = |eb e2,..., em} С V х V — множество рёбер графа; w : E ^ [0, то) — весовая функция на рёбрах. Ребро между вершинами Vi и Vj будем обозначать e(vi,v?). Будем рассматривать простые графы — без петель и кратных рёбер. Граф называется взвешенным (относительно рёбер), если каждому его ребру поставлено в соответствие число — вес ребра. Вес ребра между вершинами Vi и V? обозначается w (i, j), для вершин Vi и v?, не связанных ребром, полагается w (i, j) = то. Степень d (vi) вершины vi — количество рёбер графа, инцидентных vi. Граф разреженный, если справедливо m ^ n2. Путь в графе — чередующаяся последовательность вершин и рёбер v0, e1, v1, ..., Vk-1, ek, Vk, каждое ребро которой инцидентно двум вершинам — непосредственно предшествующей ему и непосредственно следующей за ним. Длина пути — сумма весов входящих в него рёбер. Кратчайший путь pj = ps(vi, v?) между вершинами vi и v? — путь между Vi и v? минимальной длины. Расстояние m (i,j) между vi и v? —длина кратчайшего пути между vi и v? (m (i, i) = 0, i = 1,..., n). Матрица расстояний графа— матрица Mnxra с элементами m? = m(i, j). Граф связный, если между любыми двумя его вершинами существует путь, то есть m? < то для всех i, j. Между двумя вершинами графа может существовать несколько кратчайших путей. Этот аспект в данной работе не является существенным, поэтому при всех упоминаниях кратчайшего пути будем подразумевать любой кратчайший путь. Матрица предшествования — матрица Pnxn, элемент p? которой представляет собой метку вершины, которая предшествует вершине v? в кратчайшем пути от vi до v?. То есть элементы матрицы P определяются по формуле = Vk, 3vk (pj = ...Vk, e (vk, v?), v?), p j = \ то иначе. С использованием матрицы P кратчайший путь pj для вершин vi = v? в связном графе может быть определён по рекурсивной формуле ps = f ps (vi, p j) , e (p j, vj) , vj, p j = vi, ij |Vi, e (vi, Vj), Vj, pj = Vi. Обозначим через S и будем называть сжимающей граф G0 = (V0,E0,w0) последовательность графов S = G1, G2,..., Gr, где Gp = (Vp, Ep, wp); Vp = |vf, vf,..., ; Ep = |ep, e?^,... , em(p)|. Каждый следующий граф Gp+1 последовательности получается из предыдущего Gp удалением k вершин и инцидентных им рёбер, добавлением новых рёбер и пересчётом весов рёбер между вершинами, смежными с удалёнными. Для таких графов справедливо |Vp| > |Vp+1|, p = 0,...,r — 1. Будем обозначать vp+1 вершину графа Gp+1, соответствующую вершине vp графа Gp, и ep+1 (V+1, vk+1) — реб ро графа Gp+1, соответствующее ребру ep (vj,vp) графа Gp. Граф, полученный удалением вершин vp,vp,...,vk и инцидентных им рёбер из графа Gp, будем обозначать Gp+1 = Rp (vp, vp,... , vp). Для такого графа справедливо: wp+1 (i,j) = wp(i,j) для всех i, j, таких, что vp+1,vp+1 G Vp+1. Расстояние между вершинами vp и графа Gp будем обозначать mp(i, j), а его матрицу расстояний — Mp = (mp). Наконец, обозначим AP множество всех смежных с vP вершин в графе Gp. 1.2. Постановка задачи Задача. Дан связный ненаправленный разреженный простой взвешенный граф G = (V, E,w) с неотрицательной вещественной весовой функцией на ребрах w : E ^ [0, то). Необходимо для всех пар вершин графа найти кратчайший путь между вершинами в паре, т.е. найти матрицу расстояний M и матрицу предшествования P. 2. Алгоритм поиска решения 2.1. Общая идея Принцип предлагаемого алгоритма состоит в сведении задачи на исходном графе большой размерности к задаче на графе малой размерности. Алгоритм можно разделить на три этапа: 1) сжатие — замена исходного графа графом меньшей размерности; 2) микрорешение — решение задачи о кратчайших путях на графе меньшей размерности с использованием существующих методов; 3) восстановление — перенос решения с графа меньшей размерности на исходный граф; пересчёт кратчайших расстояний для части вершин исходного графа. Такой подход требует выполнения следующих условий: а) достоверности — сжатие должно сохранять информацию о кратчайших путях исходного графа; б) скорости — выполнена всех этапов в сумме должно требовать меньше времени, чем решение задачи известными способами на исходном графе. Алгоритм, использующий похожие идеи, опубликован, например, в [6]. Для разреженных графов предлагается алгоритм «разборки и сборки графа». На этапе разборки из графа последовательно удаляются вершины, далее производится поиск решения на малом графе, после чего исходный граф собирается с получением искомых кратчайших расстояний. Отличие предлагаемого алгоритма от уже известных алгоритмов со сжатием или подменой рёбер состоит в том, что он достаточно прост, выполняет расчёт кратчайших путей сразу между всеми вершинами, при этом гарантированно находит точное решение (не является эвристическим). В частности, в [6] решается задача поиска кратчайшего пути от источника до пункта назначения (point-to-point), одной из основных целей которой является уменьшение времени запроса, тогда как время решения задачи APSP для графов большой размерности таким алгоритмом может быть весьма велико. 2.2. Р а з б о р к а Этап разборки графа является многоступенчатым и состоит в последовательном приближении исходного графа Go = (V0,Eo,wo) графами сжимающей Go последовательности S = {Gi, G2,... , Gr}. Будем рассматривать частный случай, когда каждый следующий граф Gp+1 последовательности S получается из предыдущего графа Gp удалением одной вершины. Пусть удаляемая вершина vp графа Gp имеет степень k, т.е. с ней смежны вершины vPz, z = 1,...,k. Если какой-то из кратчайших путей графа проходит через вершину vP (не считая путей от и до самой vP), то этот путь обязательно содержит подпуть вида vp , ep(vp , vP), vP, eP(vP, vp), vp, j, l G {1, 2,..., k}. Таким образом, при удалении вершины vP необходимо гарантировать сохранение кратчайших путей только p между вершинами, смежными с vi. Обозначим wmv(1'2""'h) (ij, ij) = min (wp (ij,g)+ wp (g,ij)) минимальную сумму g=1,2,...,h весов двух рёбер, соединяющих вершины vp. и vP и проходящих через одну из вершин np, vp,... , vh графа Gp. Для сохранения расстояний достаточно для всех пар вершин Vp ,vp), смежных с vP в следующем графе Gp+1 последовательности, положить ] min (wmv(i) (ij, ij), wp (ij, ij)) , если wpTW (ij, ij) < wpT^^ (ij, ij) , wp+i (ijy (1) ^wp (ij, ij) иначе. В начале алгоритма вводится матрица Pnхп с элементами Pj = то. Для сохранения информации о путях элементы матрицы P , для соответствующих номеров которых справедливо wP"v(i) (ij, ij) < min (wp (ij, ij) ,wPnv(h=i) (ij, ii)), изменяются по формуле vi, если pii; = то, Pii; , Pii; = TO. В частности, если удаляемая вершина vP смежна только с одной вершиной графа Gp, то сохранять кратчайшие пути надобности нет (так как через vp они не проходят), и в этом случае вершина vP и инцидентное ей ребро просто удаляются из графа. В качестве параметров на этапе разборки выступают dmax — максимальная степень удаляемых вершин, nmin — число вершин в самом малом графе Gr и Imax — ограничение на рост числа рёбер при удалении вершины. Вопрос совместного определения dmax, nmin и Imax является весьма объёмным, поэтому его рассмотрение остаётся вне рамок данной работы. Пусть на предмет удаления рассматривается вершина vP с k инцидентными ребрами. Обозначим через I (vP) величину изменения количества ребер при удалении вершины vP. Само удаление вершины vP уменьшит число ребер в графе на k, поэтому полагаем I (vp) = — k. Пересчёт весов ребер по формуле (1) между каждой парой vp ,vp) смежных с vP вершин изменит величину I (vP) согласно формуле p ■ I (vp) + 1, если wp (ij, ii) = то & wpTW (ij, ij) < wpT^^ (ij, ij), I (vi ) | т f px (3) 1 I (vi) иначе. Таким образом получим число, на которое изменится количество рёбер в графе Gp+1 по сравнению с Gp после удаления вершины vP. Если I (vP) > 0, число рёбер увеличится, иначе — уменьшится или останется неизменным. Использование формулы (3) предполагает применение ограничения Imax на рост числа рёбер при удалении вершины: удаляются лишь те вершины vp, для которых выполняется неравенство I (vp) ^ Imax. В процессе разборки просмотр вершин — претендентов на удаление — происходит следующим образом. Так как при dmax ^ 2 вершины степени меньше 3 удаляются в любом случае, то рассмотрение вершин происходит в порядке роста их степеней от 1 до dmax. Это позволяет уменьшить степени оставшихся вершин и ускорить работу алгоритма за счёт меньшего числа просмотров вершин со степенями, близкими к dmax. После удаления вершины vp степени смежных с ней вершин могут измениться. Поэтому для того чтобы обеспечить удаление всех вершин со степенью d (vp) ^ dmax, после удаления вершины vp рекурсивно рассматриваются бывшие смежные с ней вершины, степень которых уменьшилась в результате удаления. После завершения рекурсивного вызова просмотр вершин продолжается в обычном порядке. Алгоритм 1 разборки графа использует вспомогательный алгоритм 2 проверки и удаления вершины. Алгоритм 1. Разборка графа Вход: граф Go = (Vo,Eo,wo), |Vo| = n; dmax, nmin, Imax; РПxn = (pj), pj = то для всех i,j = l,...,n. Шаг 0. Подготовка dc =1, i = 0, nc = n, p = 0. Шаг 1. Выбор вершины 1: 2: 3: 4: Если 3vp е vp (j > i & d (vp) = dc), то 5: i = j, переход к шагу 2, 6: иначе 7: Если dc < dmax, то 8: dc = dc + 1, i = 0 и переход к шагу 1, 9: иначе 10: конец алгоритма. ШШаг 2. Проверка и удаление вершины 11: Проверка и удаление вершины (vp, nc, Imax, dmax, nmin,p, P ), переход к шагу 1. 12: Выход: граф Gr = Gp. 2.3. Микрорешение На этом этапе решается задача APSP для графа Gr последовательности S, полученного на этапе разборки. Результатом является матрица расстояний Mr графа Gr. Вводится матрица Mr = Mr и производится изменение матрицы P по формулам Если nc = nmin, то конец алгоритма, иначе то & plr ? = то, то & plr ? = то; p Pv p j pj j' p j гз wr (i, j) > mr? & ppr = то, wr(i, j) > mr? & p'r. j = то, p pp j' (5) p j r где pj — элементы матрицы предшествования Pr графа Gr. Найденные на этом этапе пути между вершинами графа Gr будут гарантированно кратчайшими, так как удаление вершин, произведённое на этапе разборки, сохраняет расстояния. То есть справедливо mj = mj = mj для всех i, j, таких, что , V е V-. Если Gr содержит всего одну вершину | V | = 1, то данный этап алгоритма пропускается и сразу выполняется сборка графа. 2.4. Сборка До начала работы данного этапа (алгоритма 3) определена последовательность графов S = {Go, Gi,... , Gr}. Здесь Go —исходный граф, Gr —наименьший граф последовательности, у которого на этапе микрорешения найдены кратчайшие пути между Алгоритм 2. Вспомогательный алгоритм проверки и удаления вершины Вход: вершина vp, текущее количество вершин nc, Imax, dmax, nmin, p, P'. Шаг 1. Проверка вершины Если d (vP) < 3, то переход к шагу 2, иначе I (vP) = — d (vP). Рассматриваются все пары вершин множества AP и изменяется значение I (vP) по формуле (3). 5: Если I (vP) ^ In 6 7 8 12 13 14 15 16 17 переход к шагу 2, иначе конец алгоритма. ШШаг 2. Удаление вершины 9: Формируется новый граф Gp+1 = Rp (vP). 10: Пересчитываются веса рёбер между вершинами графа Gp+1, соответствующими вершинам множества Ap, по формуле (1). 11: Элементы матрицы P изменяются по формуле (2), nc = nc — 1, t = p, p = p +1. Если nc = nmin, то конец алгоритма, иначе Пока nc > nmin для вершин vp, таких, что d (vp) < d , выполняем Проверка и удаление вершины (vp, nc, Imax, dmin, nmin,p, P всеми вершинами. На этапе сборки производится обратный ход от Gr к Go через графы Gr-1, Gr-2,... , G1 с расчётом кратчайших путей на каждом шаге p для вершин vr p, r— P+1 J Tr—P _ тг таких, что v^ G Vr—p+1 и vj G Vr-p. Вершина vj"-1, «добавляемая» на первом шаге к графу Gr при переходе к Gr—1, соединена ребрами с вершинами v[—1, z = 1,..., k, графа Gr—1. У Gr вычислены кратчайшие пути, т.е. известна матрица Mr = Mr. Поэтому чтобы найти матрицу расстояний Mr_ 1 графа Gr—1, надо вычислить кратчайшие пути от вершины vj"-1 до всех вершин графа Gr—1, положив остальные элементы матрицы Mr_ 1 равными соответствующим элементам МТ: mjj-1 = mjj для всех vr, v[ G V. Так как кратчайший путь от любой вершины графа Gr—1 до v[—1 проходит через одну из вершин v[~1, z = 1,... , k, кратчайшие расстояния от vj"-1 до любой вершины v[—1 графа Gr-1 можно рассчитать по формуле mr 1 (i,l) = min (wr_ 1 (i,iz)+ mr (iz, l)) . ze{1,...,fc} V / Формулы расчёта матрицы расстояний МГ-p при переходе от графа Gr-p+1 к графу Gr-p c добавлением вершины v[ p выглядят следующим образом: mjT29 = mjTP+\ v;-p+1, v[-p+1 G Vr-p+1; (6) m,r-P = m^-p = min wr-p (i, i*) + m'r-p+1 (i*, l)) , vj"-p+1 G V-p+1. (7) z€{1,...,fcj V / Обозначим x(/) номер iz для /, на котором достигается минимум формулы (7). ' r—p Элементы матрицы P , для вершин которых либо wr-p(i, /) > mJ p V wr—p(/, i) > m^ либо p^ = то V pH = то, изменяются по формулам S, px(!)l tpx(!)l, px(!)l = то; pi = , v, px(!)i = ^ '' kpx(!)i, px(!)i = то. Алгоритм 3. Сборка графа Вход: S = {Go, Gi,..., Gr}, Mr, P' 1: p = 1. 2: Пока p ^ r 3: расчёт матрицы Mr' по формулам (6), (7) и матрицы P по формулам (8) и (9); p = p + 1. 4: Выход: матрица Mo, матрица P . 2.5. Корректность алгоритма Утверждение 1. Предложенные алгоритмы «сборки и разборки графа» являются корректным, т. е. найденные в результате сборки матрицы M0 и P являются соответственно матрицами расстояний и предшествования исходного графа G0. Доказательство. Сначала докажем корректность относительно матрицы M0. Производимое на этапе разборки графа удаление вершин сохраняет расстояния между оставшимися вершинами, это следует из формулы (1). На втором этапе алгоритма находятся кратчайшие (относительно графа Go) расстояния: mj = mj для всех Vr, vr е V. На этапе сборки вычисляются кратчайшие расстояния между всеми вершинами графа; для доказательства этого достаточно показать, что при переходе от графа Gr к Gr—1 находятся кратчайшие расстояния в графе Gr—1 (в силу формулы (6) достаточно доказать это для расстояний от «добавляемой» вершины V"-1 до всех остальных вершин графа Gr—1). Это справедливо в силу сохранения расстояний для графа Gr—1 и того, что кратчайшие пути от любой вершины проходят через смежные с ней вершины, т. е. в силу формулы (7). Теперь докажем корректность относительно матрицы P'. Покажем, что на этапе микрорешения для всех вершин графа Gr находятся корректные элементы матрицы P . В силу сохранения расстояний в графе Gr кратчайший путь ps (v? , v) от v? до v содержит подпуть pj,... , v. Согласно формуле (2), если ppr ? = то, то ps (pj, j не содержит вершин, кроме pj и v?, т. е. pij = pj. Если же ppr ? = то, то, согласно (2), ps (pj, j = pj,... , ppr .j, e(p!r .j, ), , т. е. pij = ppr. ?. Расчёт по формулам (4), (5) производится для тех pj, V, vr е V, которые либо ещё не известны, либо определены неверно. Для pj = то и wr (j,/) = mj в силу (2) значения уже определены верно на этапе разборки и не требуют пересчёта, т. е. pj = p? для всех , е V. По индукции, для доказательства корректности матрицы P' достаточно показать, что при переходе от графа Gr к Gr—1 корректно определяются элементы матрицы P для «добавляемой» вершины 1. Это следует из сохранения расстояний для Gr—1, корректности P для ,v[ Е V и того, что кратчайшие пути от любой вершины проходят через смежные с ней вершины, т. е. в силу формул (8), (9). ■ pi! 3. Результаты эксперимента Все тесты проводились на компьютере с процессором Intel Core 2 Duo E8400 с частотой 3 ГГц и объемом памяти 2 Гбайт в 32-разрядной версии Windows XP. Программный код написан на языке C+—+ с использование среды разработки Borland C+—+ Builder 6. В качестве тестовых данных использовались взвешенные графы дорожных сетей США из открытого доступа (G1-G10) [7]. Из графов G1-G10 были получены связные подграфы размерностью от 103 до 104 в количестве 10 шт. для каждой размерности. Еще одним набором тестовых данных были графы дорожных сетей городов России (GR, подробные характеристики см. в [8]). Характеристики тестовых графов представлены в табл. 1. Таблица 1 Характеристики тестовых графов Группа графов Среднее кол-во вершин Среднее кол-во рёбер Средняя степень вершин Макс. степень вершин Графов G1 103 2,5 ■ 103 2,48 6 10 G2 2 ■ 103 5,21 ■ 103 2,6 5 G3 3 ■ 103 7,88 ■ 103 2,62 6 G4 4 ■ 103 1,07 ■ 104 2,68 6 G5 5 ■ 103 1,33 ■ 104 2,66 6 G6 6 ■ 103 1,58 ■ 104 2,63 7 G7 7 ■ 103 1,85 ■ 104 2,64 6 G8 8 ■ 103 2,08 ■ 104 2,6 6 G9 9 ■ 103 2,36 ■ 104 2,62 7 G10 104 2,72 ■ 104 2,72 7 GR 2,1 ■ 103 6 ■ 103 2,86 14 20 Тестирование проводилось при dmax = Imax = то, nm;n = 1. То есть при разборке удаляются вершины с любой степенью до тех пор, пока в наименьшем графе Gr не останется лишь одна вершина. Соответственно второй этап алгоритма — микрорешение — не выполняется. Разработанный алгоритм (обозначение БП) сравнивался с одним из быстрейших алгоритмов для разреженных графов — алгоритмом Дейкстры в реализации с двоичной кучей (обозначение ДД, [4]), выполняемым для всех вершин тестовых графов. Результаты тестов приведены в табл. 2. Использование предлагаемого алгоритма позволяет ускорить вычисление кратчайших путей графа в среднем в 47 раз в сравнении с алгоритмом Дейкстры. На всех тестовых графах алгоритм БП оказался быстрее алгоритма Дейстры, наибольшее по всем группам графов время счёта БП оказалось в 34 раза меньше аналогичного времени ДД. Рост максимальной степени вершины в графах последовательности S = (Gi, G2,... , Gr) во время работы алгоритма явился допустимым и не превысил 17, что говорит о невысоком росте сложности процедуры удаления вершины на этапе разборки для исследованных графов. Таблица 2 Группа графов БП, среднее время, с ДД, среднее время, с БП, макс. время, с ДД, макс. время, с Среднее ускор. БП/ДД, раз БП, макс. степень удал. верш. G1 0,03 1,5 0,05 1,7 50 11 G2 0,13 6,7 0,14 7,1 52 12 G3 0,31 16 0,33 17 52 12 G4 0,67 30 0,88 32 45 22 G5 1,1 48 1,2 52 44 16 G6 1,5 72 1,8 82 48 20 G7 2,1 97 2,2 104 46 17 G8 2,6 131 2,8 145 50 21 G9 3,7 177 4,7 189 48 24 G10 5,4 218 6,4 230 40 23 GR 0,17 7,5 0,4 18,8 45 17 Заключение Представленный алгоритм позволяет находить кратчайшие пути между всеми вершинами взвешенных ненаправленных графов. Эффективность алгоритма достигается за счёт разборки и сборки исходного графа с поиском промежуточного решения на графе малой размерности. Результаты тестов, проведённых на разреженных графах, позволяют говорить о значительном (в среднем в 47 раз) ускорении счёта в сравнении с одним из быстрых классических алгоритмов, решающих данную задачу. Объектами дальнейших исследований являются подбор параметров алгоритма на основе быстрого анализа свойств рассматриваемого графа, модификация порядка разборки и сборки графа и вопрос масштабируемости алгоритма с увеличением размерности исследуемых графов. Представляет интерес возможность адаптации использованного в алгоритме подхода для решения задач поиска кратчайших путей в направленных графах и поиска кратчайших путей с заданной погрешностью.

Ключевые слова

задача о кратчайших путях, APSP, разборка графа, сборка графа, сжатие графа, разреженные графы, APSP, graph disassembly, graph assembly, sparse graphs

Авторы

ФИООрганизацияДополнительноE-mail
Ураков Айрат РенатовичУфимский государственный авиационный технический университеткандидат физико-математических наук, доцентurakov@ufanet.ru
Тимеряев Тимофей ВалерьевичУфимский государственный авиационный технический университетаспирантtimeryaev@yandex.ru
Всего: 2

Ссылки

Bellman R. On a routing problem // Quarter. Appl. Math. 1958. No. 16. P. 87-90.
Floyd R. W. Algorithm 97: Shortest Path // Comm. ACM. 1962. No 5(6). P. 345.
Dijkstra E. W. A note on two problems in connexion with graphs // Numer. Math. 1959. No. 1. P. 269-271.
Кормен Т. Х. и др. Алгоритмы: построение и анализ. М.: Вильямс, 2006. 1296 с.
Johnson D. B. Efficient algorithms for shortest paths in sparse graph // J. ACM. 1977. No. 24. P. 1-13.
Geisberger R., Sanders P., et al. Contraction hierarchies: faster and simpler hierarchical routing in road networks // International Workshop on Experimental Algorithms (WEA 2008). Provincetown: Springer, 2008. P. 319-333.
http://www.dis.uniroma1.it/challenge9/download.shtml — 9th DIMACS Implementation Challenge — Shortest Paths (дата обращения: ноябрь 2012).
Ураков А. Р., Тимеряев Т. В. Использование особенностей взвешенных графов для более быстрого определения их характеристик // Прикладная дискретная математика. 2012. №2. C. 95-99.
 Алгоритм поиска кратчайших путей для разреженных графов большой размерности | ПДМ. 2013. № 1(19).

Алгоритм поиска кратчайших путей для разреженных графов большой размерности | ПДМ. 2013. № 1(19).

Полнотекстовая версия