Dijkstrův algoritmus

V této části si ukážeme Dijkstrův algoritmus. Jedná se o jeden z nejznámějších algoritmů a je široce používaný.

Co je to Dijkstrův algoritmus

Dijkstrův algoritmus je algoritmus pro hledání nejkratší cesty v graphu z jednoho vertexu na druhý. Vytvořil jej holandský programátor, fyzik, esejista (a nevím co dalšího ještě byl...) Edsger Dijkstra, po kterém je tento algoritmus pojmenován. Byl to velmi chytrý a vlivný člověk a hodně jeho objevů a algoritmů se běžně používá dodnes.

Nalezení nejkratší cesty v graphu se hodí na různé věci. Můžeme například chtít nalézt nejkratší cestu z jednoho místa na mapě na druhé a tak dále.

Vytvoření Weighted Graphu

Dijkstrův algoritmus pracuje s weighted graphy. Edge graphu tedy musí mít přidělenou nějakou hodnotu. V minulých částech jsme si vytvářeli jen obyčejný unweighted graph, takže si pro ukázku Dijkstrova algoritmu musíme weighted graph vytvořit. Vlastně nám jen stačí si naši třídu pro graph trochu poupravit. Protože budeme chtít uchovávat i hodnotu edgů, tak budeme při propojování vertexů muset do adjacency listu kromě samotných vertexů vkládat také hodnotu propojení (edge). Takže namísto samotných vertexů budeme v polích v adjacency listu ukládat objekty, které budou obsahovat vertex, se kterým je vertex, kterému pole patří propojený a hodnotu tohoto propojení.

Následující ukázka ukazuje třídu pro weighted graph, která vznikla upravením třídy pro graph, který jsme vytvářeli v minulých částech. Metoda addVertex zůstala stejná, metody removeEdge a removeVertex se změnili jen lehce a v metodě addEdge se teď do adjacency listu namísto samotného vertexu přidává objekt.

class WeightedGraph {
    constructor() {
        this.adjacencyList = {};
    }

    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }

    // jako parametr se metodě addEdge předává i hodnota edge
    addEdge(v1, v2, weight) {
        if (!this.adjacencyList[v1] || !this.adjacencyList[v2]) return;
        // protože pole obsahují objekty, tak se pro ověření jestli již vertexy nejsou propojené používá metoda findIndex
        // do polí v adjacency listu se u weighted graphu vkládají objekty, které obsahují propojený vertex a hodnotu propojení 
        if (this.adjacencyList[v1].findIndex(v => v.node === v2) === -1) this.adjacencyList[v1].push({node: v2, weight});
        if (this.adjacencyList[v2].findIndex(v => v.node === v1) === -1) this.adjacencyList[v2].push({node: v1, weight});
    }

    removeEdge(v1, v2) {
        if (!this.adjacencyList[v1] || !this.adjacencyList[v2]) return;
        // protože jsou v adjacency listu uloženy objekty, tak se musí porovnávat s jejich vlastností jménem node
        let index = this.adjacencyList[v1].findIndex((v) => v.node === v2);
        if (index !== -1) this.adjacencyList[v1].splice(index, 1);
        // protože jsou v adjacency listu uloženy objekty, tak se musí porovnávat s jejich vlastností jménem node
        index = this.adjacencyList[v2].findIndex((v) => v.node === v1);
        if (index !== -1) this.adjacencyList[v2].splice(index, 1);
    }

    removeVertex(vertex) {
        while (this.adjacencyList[vertex].length) {
            const adjacentVertex = this.adjacencyList[vertex].pop();
            // proměnná adjacentVertex uchovává objekt, ale do metody removeEdge chceme předat vertex
            this.removeEdge(vertex, adjacentVertex.node);
        }
        delete this.adjacencyList[vertex];
    }
}

Jak Dijkstrův algoritmus funguje

Než si do naší WeightedGraph třídy přidáme metodu pro nalezení nejkratší cesty z jednoho vertexu na druhý, tak si vysvětlíme, jak vůbec Dijkstrův algoritmus funguje. Pro tento účel jsem vytvořil následující vizuální ukázku, protože v textu se to vysvětluje špatně.

Hledáme nejkratší cestu z vertexu A k vertexu E

Chceme najít nejkratší cestu z vertexu A k vertexu E.

vertex	nejkratší cesta od A

navštívené vertexy

[]

předcházející vertex

{
    A: null,
    B: null,
    C: null,
    D: null,
    E: null,
    F: null
}

Dijkstrův algoritmus používá Priority Queue

K vytvoření Dijkstrova algoritmu potřebujeme Priority Queue. Tu jsme vytvářeli v části Binary Heap. Vytvořili jsme si Priority Queue, která je postavená na Max Binary Heap, ale pro Dijkstrův algoritmus potřebujeme Priority Queue, která je postavená na Min Binary Heap. Položky s nižší prioritou by měli mít v Priority Queue přednost. Budeme si tedy muset naši Priority Queue upravit tak, aby byla postavená na Min Binary Heap. Jediná věc, kterou v naší třídě budeme muset změnit jsou porovnávací znaménka v podmínkách u metod bubbleUp a sinkDown.

Navíc si do naší PriorityQueue třídy přidáme ještě vlastnost length, abychom mohli jednoduše zjistit, kolik Priority Queue obsahuje položek. Následující ukázka upravenou třídu pro Priority Queue ukazuje.

class Node {
    constructor(value, priority) {
        this.value = value;
        this.priority = priority;
    }
}

class PriorityQueue {
    constructor() {
        this.values = [];
        // PriorityQueue teď obsahuje také vlastnost pro počet položek, které uchovává
        this.length = 0;
    }

    enqueue(value, priority) {
        this.values.push(new Node(value, priority));
        // zvýšení počtu položek v Priority Queue
        this.length++;
        this.bubbleUp();
    }

    bubbleUp() {
        let idx = this.values.length-1;

        while (idx > 0) {
            const parentIdx = Math.trunc((idx-1)/2);

            // změnilo se porovnávací znaménko
            if (this.values[idx].priority >= this.values[parentIdx].priority) break;

            const parent = this.values[parentIdx];
            this.values[parentIdx] = this.values[idx];
            this.values[idx] = parent;

            idx = parentIdx;
        }
    }

    dequeue() {
        const max = this.values[0];
        const end = this.values.pop();
        // snížení počtu položek v Priority Queue
        this.length--;
        if (this.values.length > 0) {
            this.values[0] = end;
            this.sinkDown();
        }
        return max;
    }

    sinkDown() {
        let idx = 0;
        const length = this.values.length;
        const element = this.values[0];

        while (true) {
            let leftChildIdx = 2 * idx + 1;
            let rightChildIdx = 2 * idx + 2;
            let leftChild, rightChild;
            let swap = null;

            if (leftChildIdx < length) {
                leftChild = this.values[leftChildIdx];
                // změnilo se porovnávací znaménko
                if (leftChild.priority < element.priority) {
                    swap = leftChildIdx;
                }
            }
            if (rightChildIdx < length) {
                rightChild = this.values[rightChildIdx];
                if (
                    // změnila se porovnávací znaménka
                    (swap === null && rightChild.priority < element.priority) ||
                    (swap !== null && rightChild.priority < leftChild.priority)
                ) {
                    swap = rightChildIdx;
                }
            }

            if (swap === null) break;
            this.values[idx] = this.values[swap];
            this.values[swap] = element;
            idx = swap;
        }
    }
}

Implementace Dijkstrova algoritmu

Ukázali jsme si jak Dijkstrův algoritmus funguje a protože k jeho implementaci potřebujeme Priority Queue postavenou na Min Binary Heap, upravili jsme si naši Priority Queue třídu. Teď už se můžeme pustit do samotného kódu Dijkstrova algoritmu. Následující ukázka jej ukazuje.

class WeightedGraph {
    /* ... */

    // metoda pro zjištění nejkratší cesty mezi dvěma vertexy
    shortestPath(start, finish) {
        // vytvoření Priority Queue
        const nodes = new PriorityQueue();
        // V tomto objektu se budou ukládat vzdálenosti od startovního vertexu
        const distances = {};
        // v tomto objektu se budou ukládat předcházející vertexy vertexů
        const previous = {};
        // do tohoto pole se na konci uloží nejkratší cesta a pole se vrátí
        let path = [];
        // tato proměnná bude sloužit k ukládání získané položky z Priority Queue
        let smallest;

        // tento cyklus naplní objekt distances a přidá všechny vertexy do Priority Queue
        for (let vertex in this.adjacencyList) {
            if (vertex === start) {
                // pokud se jedná o startovní vertex, tak se mu do objektu distances uloží vzdálenost 0
                distances[vertex] = 0;
                // startovní vertex se do Priority Queue přidá s prioritou 0 (vzdáleností 0)
                nodes.enqueue(vertex, 0);
            } else {
                // pokud se nejedná o startovní vertex, tak se mu do objektu distances uloží vzdálenost jako nekonečno
                distances[vertex] = Infinity;
                // vertex se do Priority Queue přidá s prioritou nekonečno
                nodes.enqueue(vertex, Infinity);
            }
            // v objektu previous se objektu nastaví jako předchozí vertex null
            previous[vertex] = null;
        }

        // tento cyklus bude probíhat tak dlouho, dokud Priority Queue bude obsahovat nějaké položky
        while (nodes.length > 0) {
            // získání vertexu z Priority Queue (získání vertexu s nejmenší vzdáleností, který se v Priority Queue nachází)
            smallest = nodes.dequeue().value; // Priority Queue vrací Node objekt, stačí nám ale jen hodnota (vertex)

            // pokud se došlo ke konečnému vertexu, tak se našla nejkratší cesta
            if (smallest === finish) {
                // pole se naplní vertexy pomocí hodnot v objektu previous
                while (previous[smallest]) {
                    path.push(smallest);
                    smallest = previous[smallest];
                }
                // cyklus může skončit
                break;
            }

            // tento cyklus projde všechny vertexy, které jsou s vertexem smallest propojeny
            for (let neighbor of this.adjacencyList[smallest]) {
                // zjištění vzdálenosti vertexu od startovního vertexu přes vertex smallest
                let candidate = distances[smallest] + neighbor.weight;

                // pokud je zjištěná vzdálenost menší než vzdálenost v objektu distances, tak se hodnota v objektu distances změní
                if (candidate < distances[neighbor.node]) {
                    // změnění vzdálenosti vertexu od startovního vertexu v objektu distances
                    distances[neighbor.node] = candidate;
                    // nová kratší cesta vede přes vertex smallest (předchozí vertex) - vertex smallest se uloží do objektu previous
                    previous[neighbor.node] = smallest;
                    // vertex se vloží do Priority Queue s novou vzdáleností jako prioritou
                    nodes.enqueue(neighbor.node, candidate);
                }
            }
        }
        // na konec pole path se přidá startovní vertex, pole se převrátí a metoda jej vrátí
        return path.concat(smallest).reverse();
    }
}

// vytvoření graphu
const graph = new WeightedGraph();
graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("E");
graph.addVertex("F"); graph.addVertex("D"); graph.addVertex("C");
graph.addEdge("A", "B", 4); graph.addEdge("A", "C", 2); graph.addEdge("B", "E", 3);
graph.addEdge("C", "D", 2); graph.addEdge("D", "E", 3); graph.addEdge("D", "F", 1);
graph.addEdge("C", "F", 4); graph.addEdge("F", "E", 1);

// zjištění nejkratší cesty z vertexu A k vertexu E
const cesta = graph.shortestPath("A", "E");
console.log("Nejkratší cesta z vertexu A k vertexu E je:");
console.log(cesta);

distances

{
    A: undefined,
    B: undefined,
    C: undefined,
    D: undefined,
    E: undefined,
    F: undefined
}

Předchozí ukázka vizuálně ukazuje Priority Queue, kterou Dijkstrův algoritmus používá. Mohli jste si na ní všimnout jedné zajímavé věci. V ukázce Priority Queue na konci skončí neseřazená. Stalo se to kvůli tomu, že Priority Queue obsahovala více položek se stejnou prioritou a některé položky se tak nemohli umístit na správné místo. Pro dijkstrův algoritmus to tolik nevadí, nebude kvůli tomu fungovat špatně. Pokud byste se ale Priority Queue rozhodli použít někde jinde a budete do ní ukládat více položek se stejnou prioritou, tak je potřeba s těmito problémy počítat.

Doufám že vám vizuální ukázky pomohli Dijkstrův algoritmus pochopit. V příští, poslední části se pustíme do dynamického programování.

pokračovat na další část