Rajaleidmine

Rajaleidmine on lai mõiste, mille uurimisalasse kuuluvad probleemid nagu "leia lühim tee punkti A ja B vahel". Kõige sagedasemalt rakendatakse rajaleidmist, kui uuritav objekt on graaf või taandatav graafiks.

Laiuti otsing (breadth-first search ehk BFS)

Laiuti otsing on tõenäoliselt lihtsaim otsingualgoritm graafide jaoks. Olemuselt matkib laiuti otsingi vee voolamist allikast ümbruskonda.

Laiuti otsing võib leida graafis lühima tee kahe tipu vahel juhul, kui tegemist on kaaludeta graafiga (servad on väärtustamata).

Tee olemasolu kontrollimine

Alustame lihtsamast ja algoritmi olemust vähem varjavast näitest - laiuti otsingu kasutamine, et tuvastada, kas leidub tee tipu A ja B vahel.

Terve implementatsioon võib välja näha selline:

public class BFS {
    public static boolean pathExists(Vertex source, Vertex target) {
        // let's initialize a queue to store vertices that we want to visit
        Queue<Vertex> queue = new LinkedList<>();
        // let's also initialize a set to store vertices that we have already visited
        // (this is important so that we don't end up taking more than one path to visit
        //  the same vertex, which may result in infinite loops)
        Set<Vertex> visited = new HashSet<>();

        // we should obviously visit the source vertex
        queue.add(source);
        visited.add(source);

        // and we should not stop our search until we've visited
        // every node we've discovered
        while (!queue.isEmpty()) {
            // let's remove a vertex from the queue of vertices to be visited
            // and explore that
            var current = queue.poll();

            // if it turned out to be the target node,
            // we can end our search early and return `true`, indicating
            // that a path from `source` to `target` exists
            if (current == target)
                return true;

            // otherwise, we add the neighbours of the chosen vertex
            // to the queue of vertices to be explored
            // (except the ones we've already visited beforehand)
            for (var neighbour : current.getNeighbours()) {
                if (!visited.contains(neighbour)) {
                    queue.add(neighbour);
                    // this is also where we remember the nodes which we have visited
                    visited.add(neighbour);
                }
            }
        }
        // we've explored all nodes that can be reached from the
        // source node and have not returned yet - therefore, no path
        // from the source node to the target node exists
        return false;
    }
}

Olemuselt on algoritm lihtne:

külasta algustipu naabreid
ja nende naabreid...
ja nende naabreid...
(välja arvatud naabreid, mille oleme juba külastamiseks ära märkinud)
kui tipud said otsa või leidsime sihtmärgi, on otsing lõppenud

Tee leidmine

Tee leidmine on olemuselt sarnane tee olemasolu kontrollimisega - lisasammuna peame tee meelde jätma, ning lõpus tagastama.

public class BFS {
    public static Optional<List<Vertex>> findPath(Vertex source, Vertex target) {
        // let's initialize a queue to store vertices that we want to visit
        Queue<Vertex> queue = new LinkedList<>();
        // let's also initialize a set to store vertices that we have already visited
        // (this is important so that we don't end up taking more than one path to visit
        //  the same vertex, which may result in infinite loops)
        Set<Vertex> visited = new HashSet<>();
        // Additionally, we will need a map from vertex -> vertex's parent
        // denoting they step we took to reach the current node
        Map<Vertex, Vertex> parents = new HashMap<>();

        // we should obviously visit the source vertex
        queue.add(source);
        visited.add(source);

        // and we should not stop our search until we've visited
        // every node we've discovered
        while (!queue.isEmpty()) {
            // let's remove a vertex from the queue of vertices to be visited
            // and explore that
            var current = queue.poll();

            // if it turned out to be the target node,
            // we can end our search early and return the path to the node
            if (current == target)
                return reconstructPath(parents, target);

            // otherwise, we add the neighbours of the chosen vertex
            // to the queue of vertices to be explored
            // (except the ones we've already visited beforehand)
            for (var neighbour : current.getNeighbours()) {
                if (!visited.contains(neighbour)) {
                    queue.add(neighbour);
                    // this is also where we remember the nodes which we have visited
                    visited.add(neighbour);
                    parents.put(neighbour, current);
                }
            }
        }
        // we've explored all nodes that can be reached from the
        // source node and have not returned yet - therefore, no path
        // from the source node to the target node exists
        return Optional.empty();
    }

    private static Optional<List<Vertex>> reconstructPath(Map<Vertex, Vertex> parents, Vertex target) {
        // Represent the path from source to target as a list of vertices
        List<Vertex> path = new ArrayList<>();
        // Start tracing our steps back from the target vertex
        Vertex curr = target;

        while (curr != null) {
            // Add the vertex we came from to get to
            // the current vertex to the start of the path
            path.add(0, curr);

            // Set the current vertex to be the vertex we came from
            curr = parents.get(curr);
        }
        // There is no vertex we came from - therefore, we've reached
        // the source node

        return Optional.of(path);
    }
}

Algoritm on muutunud selliseks:

külasta algustipu naabreid
ja nende naabreid...
ja nende naabreid...
(välja arvatud naabreid, mille oleme juba külastamiseks ära märkinud)
ning iga külastuse kohta, jäta meelde, mis tipust just enne olime tulnud...
kui tipud said otsa või leidsime sihtmärgi, on otsing lõppenud
rekonstrueerime, kuidas soovitud tipuni jõudsime

Näide*

Kui on olemas eelmainitud BFS klass, ning sellised klassid:

public class Vertex {
    private final List<Vertex> neighbours;
    private final String name;

    public Vertex(String name) {
        this.neighbours = new ArrayList<>();
        this.name = name;
    }

    public Vertex(String name, List<Vertex> neighbours) {
        this.name = name;
        this.neighbours = neighbours;
    }

    public List<Vertex> getNeighbours() {
        return neighbours;
    }

    public void addNeighbour(Vertex neighbour) {
        neighbours.add(neighbour);
    }

    @Override
    public String toString() {
        return String.format("Vertex{%s}", name);
    }
}

public class Graph {
    private final List<Vertex> vertices;

    public Graph() {
        this.vertices = new ArrayList<>();
    }

    public Graph(List<Vertex> vertices) {
        this.vertices = vertices;
    }

    public void add(Vertex vertex) {
        this.vertices.add(vertex);
    }

    public List<Vertex> getVertices() {
        return vertices;
    }

    public void createEdge(Vertex a, Vertex b) {
        a.addNeighbour(b);
        b.addNeighbour(a);
    }
}

Siis võib laiuti otsingut kasutada niiviisi:

public class Main {

    public static void main(String[] args) {
        var a = new Vertex("a");
        var b = new Vertex("b");
        var c = new Vertex("c");
        var d = new Vertex("d");
        var f = new Vertex("e");
        var graph = new Graph(List.of(a, b, c, d, f));
        graph.createEdge(a, b);
        graph.createEdge(b, c);
        graph.createEdge(b, d);

        System.out.println(BFS.findPath(a, c));
        System.out.println(BFS.findPath(a, d));
        System.out.println(BFS.findPath(d, a));
        System.out.println(BFS.findPath(a, f));
    }
}

Väljund:

Optional[[Vertex{a}, Vertex{b}, Vertex{c}]]
Optional[[Vertex{a}, Vertex{b}, Vertex{d}]]
Optional[[Vertex{d}, Vertex{b}, Vertex{a}]]
Optional.empty

Dijkstra algoritm

Kui on vaja leida lühim tee kaaludega graafis, ei piisa enam laiuti otsingust.

Dijkstra algoritm on lihtsaim ning üks kuulsamaid rajaleidmisalgoritme, mis suudab leida vähima "kuluga" tee mistahes tipust kõikidesse teistesse tippudesse kaaludega graafis.

Tüüpiline näide Dijkstra algoritmi kasutusest on lühima tee leidmine autoteede võrgustikus.

Dijkstra algoritm on olemuselt sarnane laiuti otsingule - tippe avastatakse laiuti ning ilma heuristikata - ent erineb selle poolest, et suudab jooksvalt meelde jätta seni leitud lühimaid teid arvestades servade kaale.

Implementatsioon

Kui meil on kaalutud graaf:

public class Graph {
    private final List<Vertex> vertices;
    private final Map<Pair<Vertex, Vertex>, Integer> weights = new HashMap<>();

    public Graph() {
        this.vertices = new ArrayList<>();
    }

    public void add(Vertex vertex) {
        this.vertices.add(vertex);
    }

    public void addAll(List<Vertex> vertices) {
        this.vertices.addAll(vertices);
    }

    public List<Vertex> getVertices() {
        return vertices;
    }

    public void createEdgeWithWeight(Vertex a, Vertex b, Integer weight) {
        a.addNeighbour(b);
        b.addNeighbour(a);
        weights.put(new Pair<>(a, b), weight);
    }

    public Integer getStepCost(Vertex source, Vertex target) {
        return weights.get(new Pair<>(source, target));
    }
}

Siis võib algoritmi implementeerida niiviisi:

public class Dijkstra {
    public static Pair<Map<Vertex, Integer>, Map<Vertex, Vertex>> run(Graph graph, Vertex source) {
        // The minimum distance to the given target vertex (from the source vertex)
        Map<Vertex, Integer> dist = new HashMap<>();
        // The path that can be traced from the target vertex back to the source vertex
        // (shortest such path)
        Map<Vertex, Vertex> prev = new HashMap<>();
        // Queue of unexplored nodes - stored in a queue,
        // sorted by the distance to the given node from the source node.

        // This specific queue implementation is necessary since we need to efficiently
        // extract the node with the smallest distance from the source node from the queue
        // later on in the algorithm.

        // Java's standard library PriorityQueue is a heap-based implementation,
        // which means that the queue is kept sorted in
        // logarithmic time (log(n)) after each `queue.poll()`.
        Queue<Vertex> queue = new PriorityQueue<>(Comparator.comparingInt(dist::get));
        // The set of nodes the algorithm has visited
        Set<Vertex> visited = new HashSet<>();

        // Add each node in the graph to the queue.
        // Initialize the appropriate values associated with the nodes.
        // We use Integer.MAX_VALUE in place of infinity - we want these placeholders
        // to always compare larger than any other sensible value
        for (var vertex : graph.getVertices()) {
            dist.put(vertex, Integer.MAX_VALUE);
            prev.put(vertex, null);
            queue.add(vertex);
        }
        // The distance from the source node to the source node itself is obviously 0
        dist.put(source, 0);

        while (!queue.isEmpty()) {
            var curr = queue.poll();
            visited.add(curr);
            for (var neighbour : curr.getNeighbours()) {
                // Don't reexamine visited notes.
                if (visited.contains(neighbour))
                    continue;

                // The cost of stepping from the current examined node to its neighbour
                var alternativeCost = dist.get(curr) + graph.getStepCost(curr, neighbour);
                // If this is the first path discovered to the neighbour,
                // OR if this path costs less to reach the neighbour,
                // set this path as the path that should be taken to reach this neighbour.
                // This comparison ensures that we always keep track of only the shortest distances
                // between nodes.
                if (dist.get(neighbour) == null || alternativeCost < dist.get(neighbour)) {
                    dist.put(neighbour, alternativeCost);
                    prev.put(neighbour, curr);
                }
            }
        }

        // All nodes have been examined. Return the current state
        return new Pair<>(dist, prev);
    }
}

Pane tähele, et Dijkstra algoritmi jooksutamisel on mitu tulemust:

• Kujutis tipust V arvu X, kus V on sihtmärgiks olev tipp, ning X on algse tipu ning tipu V vahel oleva lühima tee pikkus

• Kujutis tipust Vcurr tippu Vprev, kus Vcurr -> Vprev on samm mööda lühimat teed sihtmärgi ja algse tipu vahel algse tipu poole.

Kui me ei huvitu kogu infost, mis on võimalik saada, siis on võib algoritmi jooksutami lõpetada varaselt, kui soovitud tingimused on täidetud. Levinud modifikatsioon algoritmile on otsida lühime tee vaid täpselt kahe punkti vahel.

Kasutades Dijkstra algoritmi "tagurpidi sammude" väljundit, saame leida lühima tee tippude A ja B vahel kaalutud graafis:

public class Dijkstra {

    // ...

    public static Optional<List<Vertex>> shortestPath(Graph graph, Vertex source, Vertex target) {
        var result = run(graph, source);
        var previousNodes = result.getValue();
        if (previousNodes.get(target) == null)
            return Optional.empty();
        else
            return Optional.of(reconstructPath(previousNodes, target));
    }

    private static List<Vertex> reconstructPath(Map<Vertex, Vertex> previousNodes, Vertex target) {
        List<Vertex> path = new LinkedList<>();
        Vertex current = target;
        while (current != null) {
            path.add(0, current);
            current = previousNodes.get(current);
        }
        return path;
    }
}

Näide

var graph = new Graph();
var a = new Vertex("A");
var b1 = new Vertex("B1");
var b2 = new Vertex("B2");
var c = new Vertex("C");
var x = new Vertex("X");
graph.addAll(List.of(a, b1, b2, x));
graph.createEdgeWithWeight(a, b1, 5);
graph.createEdgeWithWeight(a, b2, 10);
graph.createEdgeWithWeight(b1, c, 1);
graph.createEdgeWithWeight(b2, c, 1);

System.out.println(Dijkstra.shortestPath(graph, a, c));
System.out.println(Dijkstra.shortestPath(graph, a, x));

Väljund:

Optional[[Vertex{A}, Vertex{B1}, Vertex{C}]]
Optional.empty