Edsger Dijkstra (1969)
Edsger Dijkstra (1969)

Dijkstrův algoritmus je grafový algoritmus vytvořený nizozemským vědcem Edsgerem Wybem Dijkstrou (1930-2002), který jej navrhl v Amsterdamu po nakupování se svou snoubenkou během dvaceti minut, a to bez tužky a papíru. Slouží k vyhledání nejkratší cesty z počátečního uzlu do všech ostatních uzlů ohodnoceného grafu. Poradí si však jen s nezáporným ohodnocením hran. Často se používá v routovacích protokolech, například v algoritmu OSPF (Open Shortest Path First).

Vstupem algoritmu je nezáporně ohodnocený graf a počáteční uzel, výstupem je datová struktura (například pole nebo tabulka) obsahující délky nejkratších cest z počátečního uzlu do ostatních uzlů.

One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. Edsger Dijkstra

Kroky algoritmu

Vstup
ohodnocený graf G, počáteční uzel s
Výstup
asociativní pole D(u), udávající nejkratší vzdálenost mezi uzlem s a uzlem u
  • INICIALIZACE:
  • Vytvoř množinu uzlů X.
  • Do množiny X vlož počáteční uzel s.
  • Vytvoř asociativní pole čísel pro každý uzel D(u).
  • Inicializuj hodnoty pole D takto:
    • pro počáteční uzel s = 0
    • pro každý uzel u sousedící s počátečním uzlem s = ohodnocení hrany (s,u)
    • pro ostatní uzly = nekonečno
  • VÝPOČET:
  • Dokud nejsou v množině X všechny uzly grafu G, opakuj:
    • Najdi uzel w s minimální hodnotou D(w).
    • Přidej uzel w do množiny X.
    • Pro každý uzel u sousedící s uzlem w který není v množině X proveď:
      • hodnota D(u) je minimum ze stávající hodnoty a D(w) plus ohodnocení hrany (w,u).

Příklad

Inicializace

Vstupem algoritmu je následující graf, počátečním uzlem s je uzel A.

diagram

Všechny kroky v tabulce

Každý řádek tabulky představuje jeden krok algoritmu, ve sloupcích jsou uzly grafu G a množina X. Jednotlivé buňky obsahují hodnotu D(u) odpovídajícího uzlu u ve sloupci. Zkratka "max" označuje nekonečno.

ABCDEFmnožina X
010, A3, A4, AmaxmaxA
-8, C-4, A11, CmaxA, C
-8, C--11, C11, DA, C, D
----11, C11, DA, C, D, B
-----11, DA, C, D, B, E
------A, C, D, B, E, F

Výsledek

ABCDEF
08, C3, A4, A11, C11, D

Složitost

Dijkstrův algoritmus lze naimplementovat s asymptotickou složitostí € O(E + V \log V) €, kde €V€ je počet uzlů a €E€ je počet hran.

Implementace

package graph.algorithm.path;

import graph.model.Graph;

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

public class Dijkstra {
    /**
     * Computes all shortest paths starting from the given start node.
     * @param graph graph
     * @param start start node
     * @param weighter edge weighter
     * @param <NODE> node type
     * @param <EDGE> edge type
     * @return output with shortest path info
     */
    public static <NODE, EDGE> DijkstraOutput<NODE> dijkstra(final Graph<NODE, EDGE> graph, final NODE start, final ToIntFunction<EDGE> weighter) {
        final DijkstraOutput<NODE> output = initializeOutput(graph, start);

        final Collection<NODE> unprocessed = new LinkedList<>(graph.nodes());

        while (!unprocessed.isEmpty()) {
            // select an unprocessed node with the minimum distance and remove it
            final NODE current = Collections.min(unprocessed, Comparator.comparing(output::getDistance));
            unprocessed.remove(current);

            for (final Map.Entry<NODE, EDGE> entry : graph.successorsWithEdges(current).entrySet()) {
                // get the edge between nodes (u, v)
                final NODE next = entry.getKey();
                final EDGE edgeToNext = entry.getValue();
                // compute alternative and evaluate whether it is shorter
                final int alt = output.getDistance(current) + weighter.applyAsInt(edgeToNext);

                if (alt < output.getDistance(next)) {
                    // alternative is shorter, so use it for the shortest path
                    output.setDistance(next, alt);
                    output.setPrevious(next, current);
                }
            }
        }

        return output;
    }

    private static <NODE, EDGE> DijkstraOutput<NODE> initializeOutput(final Graph<NODE, EDGE> graph, final NODE start) {
        final DijkstraOutput<NODE> output = new DijkstraOutput<>();

        for (final NODE node : graph.nodes()) {
            // set previous node in optimal path as unknown
            output.setPrevious(node, null);
            // set distance as unknown (max possible value)
            output.setDistance(node, Integer.MAX_VALUE);
        }

        // this is zero by definition
        output.setDistance(start, 0);

        return output;
    }
}

Zdrojový kód Pokrytí testy

Reference