лучший алгоритм для определения расстояния для всех пар, где вес ребер равен 1

Question

Как сказано в заголовке, я пытаюсь реализовать алгоритм, который определяет расстояния между всеми парами узлов в данном графике.Но есть еще кое-что: (Вещи, которые могут вам помочь)

• График невзвешенный. Это означает, что все ребра можно считать имеющими вес 1 .
• |E| <= 4*|V|
• График довольно большой (не более ~ 144 глубины)
• Граф направлен
• Могут быть циклы
• Я пишу свой код на python (пожалуйста, если вы ссылаетесь на алгоритмы, код тоже подойдет:))

Я знаю о алгоритме Джонсона , Флойд-Варшале и Дейкстре для всех пар.Но эти алгоритмы хороши, когда у графа есть веса.

Мне было интересно, есть ли лучший алгоритм для моего случая, потому что эти алгоритмы предназначены для взвешенных графов.

Спасибо!

Answer 1

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

Для любого ребра, напрямую соединяющего А и С, вы точно знаете, что нет более короткого пути через третий узел В.

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

1. Те, из которых известен окончательный кратчайший путь,
2. те из которых были вычислены предварительные расстояния и
3. те, которые еще не исследованы.

При следовании за ребром e от A (1.) до C (3.) оригинальный Дейкстра будет перемещать узел C из (3.) в (2.). Поскольку вышеуказанный атрибут сохраняется во всех ваших графиках, вы можете добавить его непосредственно в набор (1.), что более эффективно.

Вот важное замечание: описанная выше процедура в основном представляет собой BFS (поиск в ширину), то есть вы можете найти расстояние от некоторого фиксированного узла v до любого другого узла в O(|V| + |E|).

Вы не упомянули в своем первоначальном вопросе, что график был в основном сеткой с некоторыми дырами в нем. Это еще более сильное требование, и я уверен, что вы можете его использовать. Быстрый поиск «кратчайшего пути графа сетки» дает этой статьи , которая обещает O(sqrt(n)) в лучшем случае. Поскольку указанная вами проблема достаточно хорошо структурирована, я почти уверен, что есть еще несколько статей, которые вы можете рассмотреть.

Answer 2

Запустите поиск в ширину для каждого узла. Общее время: O (| V | | E |) = O (| V | ² ), что является оптимальным.

Answer 3

Я предлагаю вам попробовать networkx, похоже, он отлично работает с 1000 узлами.

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

http://networkx.lanl.gov/reference/algorithms.shortest_paths.html

Вот пример с 10 узлами:

from random import random
import networkx as nx
G=nx.DiGraph()
N=10
#make a random graph
for i in range(N):
    for j in range(i):
        if 4*random()<1:
            G.add_edge(i,j)

print G.adj
print nx.all_pairs_shortest_path(G)
print nx.all_pairs_shortest_path_length(G)

#output:
#Graph ADJ={0: {}, 1: {}, 2: {}, 3: {0: {}, 2: {}}, 4: {}, 5: {0: {}, 3: {}, 4: {}}, 6: {0: {}, 1: {}, 4: {}}, 7: {2: {}, 4: {}, 6: {}}, 8: {1: {}}, 9: {2: {}, 5: {}}}
#PAIRS={0: {0: [0]}, 1: {1: [1]}, 2: {2: [2]}, 3: {0: [3, 0], 2: [3, 2], 3: [3]}, 4: {4: [4]}, 5: {0: [5, 0], 2: [5, 3, 2], 3: [5, 3], 4: [5, 4], 5: [5]}, 6: {0: [6, 0], 1: [6, 1], 4: [6, 4], 6: [6]}, 7: {0: [7, 6, 0], 1: [7, 6, 1], 2: [7, 2], 4: [7, 4], 6: [7, 6], 7: [7]}, 8: {8: [8], 1: [8, 1]}, 9: {0: [9, 5, 0], 2: [9, 2], 3: [9, 5, 3], 4: [9, 5, 4], 5: [9, 5], 9: [9]}}
#LENGTHS={0: {0: 0}, 1: {1: 0}, 2: {2: 0}, 3: {0: 1, 2: 1, 3: 0}, 4: {4: 0}, 5: {0: 1, 2: 2, 3: 1, 4: 1, 5: 0}, 6: {0: 1, 1: 1, 4: 1, 6: 0}, 7: {0: 2, 1: 2, 2: 1, 4: 1, 6: 1, 7: 0}, 8: {8: 0, 1: 1}, 9: {0: 2, 2: 1, 3: 2, 4: 2, 5: 1, 9: 0}}

Answer 4

Я предполагаю, что график является динамическим; в противном случае нет причин не использовать Floyd-Warshall для предварительного вычисления расстояний между парами на таком маленьком графике;)

Предположим, у вас есть сетка точек (x, y) с 0 <= x <= n, 0 <= y <= n. После удаления ребра E: (i, j) <-> (i + 1, j) вы разделяете строку j на множества A = {(0, j), ..., (i, j)}, B = {(i + 1, j), ..., (n, j)} так, чтобы точки a в A, b в B были вынуждены обойти E - поэтому вам нужно только пересчитать расстояние для всех пары (a, b) в (A, B).

Может быть, тогда вы сможете предварительно вычислить Флойд-Варшалл и использовать что-то вроде этого, чтобы сократить пересчет до O (n ^ 2) (или около того) за модификацию графа ...

Answer 5

Я хотел бы отослать вас к следующей статье: «Алгоритмы субкубических затрат для задачи кратчайшего пути всех пар» Тадао Такаока. Существует последовательный алгоритм с субкубической сложностью для графов с удельным весом (фактически максимальный вес ребра = O (n ^ 0,624)).

Answer 6

Как насчет алгоритма Варшалла, со следующей очень простой реализацией:

def warshall(graph):
  n = graph.numNodes+1
  W = [ [graph.w(i,j) for j in graph.V()] for i in graph.V() ]
  for k in range(1,n): 
    for i in range(1,n):
      for j in range(1,n):
        W[i][j] = min( W[i][j] , W[i][k]+W[k][j] )
  return W

, где

• V() дают все вершины графа
• w(i,j) возвращает значение края (i, j) - в вашем случае все 1 или 0
• numNodes дают число узлов графа.

сложность равнаоднако O (n ^ 3)

Answer 7

Я не знаю, как вы можете измерить расстояние, если все ребра не взвешены, но вы хотите взглянуть на алгоритм Эдмонда Блоссом V.Вы хотите посмотреть на http://code.activestate.com/recipes/221251-maximum-cardinality-matching-in-general-graphs. Вот что-то похожее: http://wilanw.blogspot.com/2009/09/maximumminimum-weighted-bipartite.html.

Answer 8

def from_vertex(v, E):
    active = [v]
    step = 0
    result = {v:0}
    while active:
        step += 1
        new_active = []
        for x in active:
            for nh in E[x]:
                if nh not in result:
                    new_active.append(nh)
                    result[nh] = step + 1
        active = new_active
    return result

Обычно вы выполняете заливку из каждой вершины и в результате получаете минимальное расстояние от любой другой достижимой вершины до этой.

Answer 9

После быстрого пролистывания Руководства по разработке алгоритма , вот что говорит Скиена (из главы 15.4 - Кратчайший путь). Неудивительно, что к такому же выводу приходят многие из вас, но и некоторые другие идеи

Основным алгоритмом нахождения кратчайшего пути является алгоритм Джикстры ...

Является ли ваш граф взвешенным или невзвешенным? Если ваш граф невзвешенный, простой поиск в ширину, начиная с исходной вершины, найдет кратчайший путь ко всем остальным вершинам за линейное время ...

Он продолжает упоминать другие случаи, которые могут вас заинтересовать (например, что, если вход представляет собой набор геометрических препятствий? Вам нужен кратчайший путь между всеми парами точек?), Но в этих случаях он также завершает как у вас: алгоритм Джикстры или алгоритм Флойда-Варшалла.

В зависимости от вашего использования, вы также можете посмотреть Transitive Closures , которые имеют дело с достижимостью, и использовать аналогичные алгоритмы.

Answer 10

В проекте Python Graph:

http://code.google.com/p/python-graph/

Вы можете найти мою реализацию алгоритма A * с поддержкой хинтинга-эвристики. Это особенно подходит для обхода препятствий в двух измерениях, поскольку алгоритм хинтинга не должен быть чем-то большим, чем теорема Пифогра.

Я думаю, что это сделало бы все, что тебе нужно. Если вам не нравятся абстракции графа, используемые этим проектом, вы можете повторно использовать алгоритм. Это написано очень общим способом.