Алгоритм Флойда — еще один метод поиска кратчайшего пути в графе.

Я уже реализовал алгоритм Дейкстры примерно две недели назад. Однако Дейкстра не работает с графами с отрицательными весами на ребрах.

Помните, у нас был набор кратчайших путей, найденных до сих пор, и любое расширение пути привело бы к более длинному пути. Довольно легко найти контрпример и сломать алгоритм, если у вас отрицательные веса.

Алгоритм Флойда работает даже с отрицательными весами. Заранее он может определить, есть ли в графе отрицательный цикл. Обратите внимание, что граф с отрицательным циклом, содержащим вершины 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')