Algorytm Dijkstry

Algorytm Dijkstry – Każdego dnia, ktoś z nas podejmuję, jakąś drogę.
Może z domu 🏠 do pracy, ze szkoły do sklepu 🛍️, a może nawet gdzieś dużo dalej do innego kraju na cudowne wakacje 🌴🏖.
W zaganianej codzienności przeważnie staramy się wybierać najkrótszą drogę.
Aby wytypować najkrótszą drogę do naszego celu podróży, przeważnie sięgamy za mapę papierową lub nawigację GPS 🧭.

Aby znaleźć tę najkrótszą trasę, możemy się posłużyć algorytmem Dijkstry,
który sprawdzi się do tego idealnie.
Zdradzę Ci nawet, że GPS również z niego korzysta 😉

W tym materiale chcę Ci powiedzieć – czym jest algorytm Dijkstry oraz kto go stworzył.
Dowiesz się również jak samodzielnie napisać ten algorytm w Javie.

Java – Algorytm Dijkstry – wprowadzenie

Z tego materiału dowiesz się:

  • Czym jest algorytm Dijkstry?
  • Kim jest Edsger W. Dijkstra?
  • Czym jest graf ważony?
  • Jak powinien działać algorytm Dijkstry?
  • Jak napisać w Javie algorytm Dijkstry?

Algorytm Dijkstry

Algorytm Dijkstry – to znany algorytm grafowy, który służy do znalezienia najkrótszej ścieżki, między dwoma punktami w grafie ważonym. Algorytm rozpoczyna się w punkcie początkowym i odwiedza sąsiednie punkty, wybierając ten o najmniejszej odległości.
Następnie kontynuuje odwiedzanie sąsiednich punktów, aż do osiągnięcia punktu końcowego.

 

Dijkstra algorithm algorytm

Algorytm Dijkstry jest powszechnie stosowany w takich aplikacjach jak routing sieciowy, nawigacja GPS, a nawet w branży gier do znajdowania optymalnych ścieżek na mapach gier.

Algorytm Dijkstry – Edsger W. Dijkstra

Nazwa algorytmu Dijkstry, pochodzi od nazwiska jego twórcy, holenderskiego informatyka – Edsgera W. Dijkstry.

Algorytm został opracowany przez niego w 1956 roku. W wywiadzie dla Communications of the ACM w 2001 roku Dijkstra powiedział, że stworzył ten algorytm chcąc znaleźć najszybszą drogę z jednego do drugiego miasta w Holandii.

Algorytm Dijkstry – Graf ważony

Aby zrozumieć algorytm Dijkstry, warto najpierw powiedzieć kilka słów o samym grafie ważonym.

Graf ważony to połączone ze sobą linią (krawędzią) punkty. Każda linia łącząca ma przypisaną wartość (wagę), która jest kosztem osiągnięcia tej drogi.

Można porównać to do mapy dróg między miastami, gdzie każdy punkt będzie miał różną „punktację” zależną od odległości, kosztu, korków.

Algorytm Dijkstry – Działanie

Za nim napiszemy nasz algorytm, określmy kroki, które będą musiały być spełnione, aby algorytm Dijkstry działał poprawnie.

  1. Wybranie punktu startowego.
  2. Sprawdzenie, jakie drogi są dostępne do wyboru. Przypisanie punktom – do których nie da się dojść – wartość równą nieskończoności. Natomiast tym punktom sąsiadującym z punktem startowym, należy przypisać wagę równą wadze krawędzi prowadzącej do tych punktów.
  3. Wybranie punktu z najmniejszą wagą i oznaczenie go jako „odwiedzonego”.
  4. Dla każdego sąsiada wybranego punktu, obliczenie wagi nowej ścieżki prowadzącej przez ten punkt i porównanie jej z wagą aktualną. Wybranie tej drogi, która ma najmniejszą wagę.
  5. Powtórzenie kroków 4 i 5, do momentu, aż wszystkie punkty zostaną odwiedzone lub dopóki nie zostanie odnaleziona ścieżka prowadząca do celu.

Algorytm Dijkstry – Java

Algorytm Dijkstry jest dość złożonym algorytmem, dlatego posłużę się klasami pomocniczymi:

  • Vertex – reprezentuje wierzchołki w grafie, wraz z ich wagami.
public class Vertex {
    private int id;
    private int weight;

    public Vertex(int id, int weight) {
        this.id = id;
        this.weight = weight;
    }

    public int getId() {
        return id;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }
}
  • Edge – reprezentuje krawędzie w grafie, wraz z wagą i wierzchołkami, które łączy.
public class Edge {
    private Vertex src;
    private Vertex dest;
    private int weight;

    public Edge(Vertex src, Vertex dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }

    public Vertex getSrc() {
        return src;
    }

    public Vertex getDest() {
        return dest;
    }

    public int getWeight() {
        return weight;
    }
}

  • Graph – reprezentuje graf wraz z listą wierzchołków i listą krawędzi. Klasa ta udostępnia również metodę dostarczającą listę, dla wskazanego wierzchołka, sąsiednich wierzchołków.
public class Graph {
    private List<Vertex> vertices;
    private List<Edge> edges;

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

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

    public List<Edge> getEdges() {
        return edges;
    }

    public List<Vertex> getNeighbors(Vertex v) {
        List<Vertex> neighbors = new ArrayList<>();
        for (Edge e : edges) {
            if (e.getSrc().equals(v)) {
                neighbors.add(e.getDest());
            }
        }
        return neighbors;
    }
}
public class DijkstraAlgorithm {
    public static void dijkstra(Graph graph, Vertex start) {
        PriorityQueue<Vertex> pq = new PriorityQueue<>(Comparator.comparing(Vertex::getWeight));
        for (Vertex v : graph.getVertices()) {
            if (v.equals(start)) {
                v.setWeight(0);
            } else {
                v.setWeight(Integer.MAX_VALUE);
            }
            pq.offer(v);
        }

        while (!pq.isEmpty()) {
            Vertex u = pq.poll();
            for (Vertex v : graph.getNeighbors(u)) {
                int altDist = u.getWeight() + getEdgeWeight(graph, u, v);
                if (altDist < v.getWeight()) {
                    pq.remove(v);
                    v.setWeight(altDist);
                    pq.offer(v);
                }
            }
        }

        // print the shortest distances
        System.out.println("Shortest distances from node " + start.getId() + " to:");
        for (Vertex v : graph.getVertices()) {
            System.out.println(v.getId() + ": " + v.getWeight());
        }
    }

    private static int getEdgeWeight(Graph graph, Vertex u, Vertex v) {
        for (Edge e : graph.getEdges()) {
            if (e.getSrc().equals(u) && e.getDest().equals(v)) {
                return e.getWeight();
            }
        }
        throw new IllegalArgumentException("Edge not found");
    }

    public static void main(String[] args) {
        Vertex v0 = new Vertex(0, Integer.MAX_VALUE);
        Vertex v1 = new Vertex(1, Integer.MAX_VALUE);
        Vertex v2 = new Vertex(2, Integer.MAX_VALUE);
        Vertex v3 = new Vertex(3, Integer.MAX_VALUE);
        Vertex v4 = new Vertex(4, Integer.MAX_VALUE);
        List<Vertex> vertices = Arrays.asList(v0, v1, v2, v3, v4);

        Edge e01 = new Edge(v0, v1, 10);
        Edge e03 = new Edge(v0, v4, 5);
        Edge e04 = new Edge(v1, v2, 1);
        Edge e05 = new Edge(v1, v4, 2);
        Edge e06 = new Edge(v2, v3, 4);
        Edge e07 = new Edge(v3, v4, 3);

        List<Edge> edges = Arrays.asList(e01, e03, e04, e05, e06, e07);

        Graph graph = new Graph(vertices, edges);

        dijkstra(graph, v0);
    }
}

Przyjrzyjmy się naszej głównej klasie, implementującej algorytm Dijkstry.

  • W pierwszym kroku zostaje zainicjalizowana najkrótsza odległość do wszystkich wierzchołków maksymalną wartością, jaką przyjmuje Integer (2147483647), z wyjątkiem wierzchołka źródłowego, który jest ustawiony na zero.
  • Wierzchołki dodawane są do wcześniej utworzonej, kolejki priorytetowej (sterty) wierzchołków, gdzie priorytet jest oparty na najmniejszej odległości od wierzchołka źródłowego.
  • Następnie w pętli while, tak długo, dopóki kolejka priorytetów nie jest pusta, algorytm wykonuje następujące czynności:
    • Usuwa z kolejki priorytetowej wierzchołek o najkrótszej odległości.
    • Dla każdego z sąsiadów tego wierzchołka oblicza odległość do sąsiada przez bieżący wierzchołek i aktualizuje najkrótszą odległość sąsiada, jeśli nowa odległość jest krótsza od bieżącej najkrótszej odległości. Jeśli najkrótsza odległość sąsiada zostanie zaktualizowana, jest on dodawany do kolejki priorytetowej.
  • W końcowym etapie w pętli wyświetlanie są najkrótsze dystanse od naszego wierzchołka źródłowego do poszczególnych wierzchołków.

Java – Queue – Kolejka

W ramach tego materiału zajmiemy się przede wszystkim algorytmem Dijkstry – natomiast kompletny materiał dotyczący kolejek znajdziesz poniżej.

➡ ZOBACZ 👉: Kolejka (Queue) – samouczek, FIFO krok po kroku

Algorytm Dijkstry – Podsumowanie

W ramach tego materiału dowiedzieliśmy się, czym jest algorytm Dijkstry i kim jest jego twórca.
Wiemy, że algorytm Dijkstry pomaga wyznaczyć najkrótszą możliwą drogę między dwoma punktami na grafie ważonym.

Bliżej poznaliśmy również samą strukturę algorytmu i jego działanie.

Kierunek Java

W serii o Javie zapoznajesz się z podstawowymi tematami o Javie. Jeżeli chcesz bardziej kompleksowo zagłębić się w temat Javy, poczytać, posłuchać o Javie, to zachęcam Cię do zapoznania się z moim kursem „Kierunek Java”:

➡ ZOBACZ 👉: Kierunek Java


20+ BONUSOWYCH materiałów z programowania

e-book – „8 rzeczy, które musisz wiedzieć, żeby dostać pracę jako programista”,
e-book – „Java Cheat Sheet”,
checklista – „Pytania rekrutacyjne”
i wiele, wiele wiecej!

Jak zostać programistą

No comments
Share:

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *