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

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

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

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

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

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

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

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

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

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

Как насчет алгоритма 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)

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

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

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

В проекте Python Graph:

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

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

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

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

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

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

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

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

 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 

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