Алгоритм Флойда — еще один метод поиска кратчайшего пути в графе.
Я уже реализовал алгоритм Дейкстры примерно две недели назад. Однако Дейкстра не работает с графами с отрицательными весами на ребрах.
Помните, у нас был набор кратчайших путей, найденных до сих пор, и любое расширение пути привело бы к более длинному пути. Довольно легко найти контрпример и сломать алгоритм, если у вас отрицательные веса.
Алгоритм Флойда работает даже с отрицательными весами. Заранее он может определить, есть ли в графе отрицательный цикл. Обратите внимание, что граф с отрицательным циклом, содержащим вершины U, V, не имеет кратчайшего пути между U, V.
Какой из них является кратчайшим путем между (0, 1)?length(0, 1) = -1
length(0, 1, 2, 0, 1) = -2
length(0, 1, 2, 0, 1, 2, 0, 1) = -3
Идея алгоритма заключается в итеративном построении кратчайших путей между некоторыми вершинами U и V, используя лишь ограниченный набор вершин. Когда это множество расширяется другой вершиной W, мы можем либо получить более короткий путь через W, либо у нас уже есть лучший.
shortest(U, V) = min( shortest(U, V), shortest(U, W) + shortest(W, V) )
Вы можете видеть, что связь является рекурсивной. Итеративное построение, используемое в алгоритме, является еще одним примером техники динамического программирования.
https://github.com/coells/100days
https://notebooks.azure.com/coells/libraries/100days
алгоритм
def floyd(graph): # initialize matrix distance = nx.adjacency_matrix(graph).todense().astype(float) distance[distance == 0] = np.inf np.fill_diagonal(distance, 0) # find shortest paths for k, i, j in product(range(len(graph)), repeat=3): distance[i, j] = min(distance[i, j], distance[i, k] + distance[k, j]) # negative cycle detection if i == j and distance[i, j] < 0: return k, i, 'negative cycle detected' # shortest paths return { (i, j): distance[i, j] for i, j in product(range(len(graph)), repeat=2) if i != j and not np.isinf(distance[i, j]) }
график
Направленный граф; черные ребра имеют вес = 1, красные ребра имеют вес = -1.
> graph = generate_graph(5, edge_prob=.4, pos_weight_prob=.7) > floyd(graph) {(0, 1): 0.0, (0, 2): -1.0, (0, 3): -2.0, (0, 4): -1.0, (1, 0): 1.0, (1, 2): 0.0, (1, 3): -1.0, (1, 4): 0.0, (2, 0): 2.0, (2, 1): 1.0, (2, 3): -1.0, (2, 4): 0.0, (3, 4): 1.0}
график с отрицательным циклом
Направленный граф; черные ребра имеют вес = 1, красные ребра имеют вес = -1.
> graph = generate_graph(5, edge_prob=.4, pos_weight_prob=.6) > floyd(graph) (1, 4, 'negative cycle detected')