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

Ответ 1

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

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

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

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

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

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

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)

Ответ 5

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

Ответ 6

Я предполагаю, что график является динамическим; в противном случае нет оснований не использовать 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).

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

Ответ 7

Я предлагаю вам попробовать 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}}

Ответ 8

В проекте Python Graph:

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

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

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

Ответ 9

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

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

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

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

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

Ответ 10

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

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