Stephen Warshall (1969)
Stephen Warshall (1969)

Grafový algoritmus Floyd-Warshall slouží k nalezení nejkratších cest mezi všemi dvojicemi uzlů. Během roku 1962 byl v různých podobách představen několika na sobě nezávislými autory. Princip algoritmu však lze vysledovat až do roku 1956 (Kleenův algoritmus).

Algoritmus si bohužel neporadí se zápornými cykly uvnitř grafu - proto se pro jeho správnou funkci předpokládá, že tam žádné nejsou.

Kroky algoritmu

Inicializace

V paměti se inicializuje čtvercová matice o velikosti € n \times n €, kde € n € je počet uzlů. Každý řádek a sloupec odpovídá jednomu uzlu, zatímco číslo v matici představuje minimální nalezenou vzdálenost mezi touto dvojicí uzlů.

Matice se inicializuje dle následujících pravidel:

  • pro všechny hrany vedoucí z uzlu ve sloupci a do uzlu na řádku b se vyplní délka této hrany
  • na hlavní diagonálu se vyplní nuly, protože vzdálenost z uzlu do toho samého uzlu je 0
  • do ostatních buněk se vyplní nekonečno, protože vzdálenost mezi těmito uzly není definována

Výpočet

Výpočet se skládá ze třech vnořených cyklů. V každé iteraci hlavního cyklu se hledá možnost zkrácení cesty mezi všemi dvojicemi uzlů "oklikou" přes jeden uzel vybraný hlavním cyklem. Jsou samozřejmě ignorovány neplatné možnosti, kdy danou zkratkou nelze projít, protože mezi vyhodnocovanými uzly nevede žádná cesta. Pokud je však nalezená "zkratka" výhodnější, záznam v matici se aktualizuje a nalezená zkratka se uloží, aby bylo možné později nejkratší nalezenou cestu zrekonstruovat.

diagram

Implementace (Java)

package graph.algorithm.path;

import graph.model.Graph;

import java.util.*;
import java.util.function.ToIntFunction;

/**
 * Implementation of Floyd-Warshall`s algorithm.
 */
public final class FloydWarshall {
    /**
     * Finds all pair`s shortest paths.
     * @param graph original graph
     * @param weighter edge weight provider
     * @return output containing the shortest paths between any two of the graph nodes
     */
    public static <N, E> FloydWarshallOutput calculate(final Graph<N, E> graph, final ToIntFunction<E> weighter) {
        final List<N> nodes = new ArrayList<>(graph.nodes());
        final FloydWarshallMatrix<Integer, N> matrix = new FloydWarshallMatrix<>(nodes.size());

        for (int iX = 0; iX < matrix.size(); iX++) {
            for (int iY = 0; iY < matrix.size(); iY++) {
                final N xNode = nodes.get(iX);
                final N yNode = nodes.get(iY);

                if (iX == iY) {
                    // the same node - distance is zero
                    matrix.setMinimumDistance(iX, iY, 0);
                    matrix.setPredecessor(iX, iY, xNode);
                } else {
                    final E edge = graph.edgeIncidentWithNodes(xNode, yNode);

                    if (edge != null) {
                        // edge is defined - define distance
                        final int distance = weighter.applyAsInt(edge);
                        matrix.setMinimumDistance(iX, iY, distance);
                        matrix.setPredecessor(iX, iY, xNode);
                    }
                }
            }
        }

        for (int iDetour = 0; iDetour < matrix.size(); iDetour++) {
            for (int iX = 0; iX < matrix.size(); iX++) {
                for (int iY = 0; iY < matrix.size(); iY++) {
                    final Optional<Integer> detourPart1 = matrix.get(iX, iDetour);
                    final Optional<Integer> detourPart2 = matrix.get(iDetour, iY);

                    if (detourPart1.isPresent() && detourPart2.isPresent()) {
                        final int detourDistance = detourPart1.get() + detourPart2.get();
                        final Optional<Integer> currentDistance = matrix.get(iX, iY);

                        if (!currentDistance.isPresent() || detourDistance < currentDistance.get()) {
                            // the detour is better than what we have so far
                            final N detourNode = nodes.get(iDetour);
                            matrix.setMinimumDistance(iX, iY, detourDistance);
                            matrix.setPredecessor(iX, iY, detourNode);
                        }
                    }
                }
            }
        }

        return new FloydWarshallOutput<N>() {
            @Override
            public Optional<Integer> getMinimalDistance(final N a, final N b) {
                final int iA = nodes.indexOf(a);
                final int iB = nodes.indexOf(b);

                if (iA == -1 || iB == -1) {
                    // unknown node
                    return Optional.empty();
                }

                return matrix.get(iA, iB);
            }

            @Override
            public Optional<List<N>> getShortestPath(final N a, final N b) {
                final int iTarget = nodes.indexOf(a);
                int iStart = nodes.indexOf(b);

                if (iStart == -1 || iTarget == -1) {
                    // unknown node
                    return Optional.empty();
                }

                final List<N> result = new LinkedList<>();

                while (true) {
                    result.add(nodes.get(iStart));

                    if (iStart == iTarget) {
                        // we reached the target node
                        // (we must reverse the path, because we started at the end)
                        Collections.reverse(result);
                        return Optional.of(result);
                    }

                    final Optional<N> parent = matrix.getParent(iTarget, iStart);

                    if (parent.isPresent()) {
                        // advance to next node
                        iStart = nodes.indexOf(parent.get());
                    } else {
                        // this should never happen as matrix is under our control
                        return Optional.empty();
                    }
                }
            }
        };
    }

}

Zdrojový kód Pokrytí testy

package graph.algorithm.path;

import java.util.ArrayList;
import java.util.List;
import java.util.Optional;

import static java.util.Collections.nCopies;

public class FloydWarshallMatrix<VALUE, PARENT> {
    private final List<VALUE> matrix;
    private final List<PARENT> parent;
    private final int n;

    public FloydWarshallMatrix(final int n) {
        this.matrix = new ArrayList<>(nCopies(n * n, null));
        this.parent = new ArrayList<>(nCopies(n * n, null));
        this.n = n;
    }

    public int size() {
        return n;
    }

    public Optional<VALUE> get(final int x, final int y) {
        return Optional.ofNullable(matrix.get(map(x, y)));
    }

    public Optional<PARENT> getParent(final int x, final int y) {
        return Optional.ofNullable(parent.get(map(x, y)));
    }

    public void setMinimumDistance(final int x, final int y, final VALUE value) {
        matrix.set(map(x, y), value);
    }

    public void setPredecessor(final int x, final int y, final PARENT value) {
        parent.set(map(x, y), value);
    }

    private int map(final int x, final int y) {
        return x * n + y;
    }
}

Zdrojový kód Pokrytí testy

Příklad

Mějme například tento graf:

diagram

Matice se inicializuje do následující podoby (v řádcích je první uzel, ve sloupcích druhý):

ABCD
A01--
B-02-
C--03
D47-0

Po výpočtu vypadá matice takto:

ABCD
A0136
B9025
C7803
D4570

Z matice lze tedy například přečíst, že nejkratší cesta z uzlu A do uzlu C má délku 3, nebo že nejkratší cesta z uzlu B do uzlu A má délku 9. Také je patrné, že je celá vyplněná, což znamená, že pro každé dva uzly existuje nějaká cesty, která je spojuje.

Pokud se společně s maticí nejkratších délek udržuje i seznam předchůdců, vypadá takto:

ABCD
AAABC
BDBBC
CDDCC
DDABD

Matici předchůdců lze využít k rekonstrukci nejkratší cesty mezi dvěma uzly. Tato cesta se rekonstruuje pozpátku, tedy od cíle směrem k prvnímu uzlu. Pokud například hledáme cestu z uzlu B do uzlu A, postupujeme takto:

  • hledáme cestu mezi uzly B a A
  • hodnota v řádku B a sloupci A je D - tzn. cesta bude B - ??? - D - A
  • dále hledáme cestu mezi uzly B a D
  • hodnota v řádku B a sloupci D je C - tzn. cesta bude B - ??? - C - D - A
  • dále hledáme cestu mezi uzly B a C
  • hodnota v řádku B a sloupci C je B - dorazili jsme na počátek, hledaná nejkratší cesta bude B - C - D - A

Reference