W poprzednim artykule z cyklu algorytmiki poruszyliśmy zagadnienie wyszukiwania najkrótszej ścieżki w grafie (przeszukiwanie wszerz). Zrobimy kolejny krok badawczy w tym kierunku i zaprezentuję jeszcze jeden algorytm, bardzo popularny swoją drogą, i bardzo cenny do wyznaczania ścieżki od punktu A do punktu B w grafie ważonym. Temat niniejszego artykułu to algorytm Dijkstry!

Spoiler alert: artykuł będzie ZNACZNIE większy!!!

ALGORYTM DIJKSTRY. JESZCZE NIERAZ O NIM USŁYSZYSZ!

Algorytm znany, lubiany i szanowany. Powstały z inicjatywy bardzo ważnej postaci w nauce informatycznej, Pana Edsgera Dijkstry, informatyka holenderskiego pochodzenia, który niestety zmarł już ponad 20 lat temu...Sprawdźmy co ten człowiek takiego wynalazł, że jest powszechnie wykorzystywane w praktyce.

Problem: odnalezienie odpowiedniego węzła w grafie ważonym na podstawie podanego kryterium

Ten algorytm także rozwiązuje problem wyszukania najkrótszej ścieżki (ang. "shortest path problem"), z tym że on uwzględnia wagi krawędzi w przeciwieństwie do przeszukiwania wszerz! "Tak po polsku?", możesz teraz myśleć. Otóż musicie wiedzieć, drodzy adepci informatyki i algorytmiki, że królowa nauk dysponuje już od dawien dawna jeszcze jednym rodzajem grafu. Jest nim graf ważony. Charakteryzuje się tym, że każdej krawędzi (tzn. połączeniu pomiędzy jednym węzłem a drugim), przypisywana jest pewna liczba naturalna (czyt. liczba całkowita większa bądź równa zero). Podana taka wartość oznacza koszt lub "wysiłek" jaki trzeba ponieść, aby dostać się przez relację od aktualnego węzła do docelowego. Dla lepszego zobrazowania sytuacji, możecie sobie wyobrazić próbę przejścia na drugą stronę rzeki i macie do wyboru: albo spróbować przepłynąć przez rzekę na drugą stronę, albo pójść kawałek dalej i przejść przez most. Przepłynięcie wpław będzie o wiele bardziej wymagające niż skorzystanie z mostu, więc można pomyśleć o skali 10:1 (imaginując). To właśnie będzie reprezentować nasz koszt czy wagę krawędzi i algorytm Dijkstry sobie doskonale poradzi z takim rozróżnieniem. "Pathfinding" to jego specjalność!

BEZ TEGO TO NIE PÓJDZIE!

Muszę nieco przyblokować Wasz "hurra optymizm", jeśli taki pojawił się w głowach. Algorytm ten, choć spełnia postawione mu wymagania, to jednak nie przyniesie dobrych rezultatów dla każdego grafu. Warunkiem krytycznym do prawidłowego zwrócenia rozwiązania jest to, aby graf był acyklicznym grafem skierowanym. Graf skierowany to taki, którego krawędzie posiadają kierunek bądź zwrot określający od jakiego do jakiego węzła można przejść i co ważne, jest to przejście "jednokierunkowe". To znaczy, że jeśli krawędź od węzła A "wskazuje" na węzeł B, to można przejść od węzła A do węzła B, ale nie na odwrót!!! Acykliczność z kolei to termin określający graf nieposiadający żadnych cykli, a cykl z kolei to jest każda skończona ścieżka idąca do innego węzła, w taki sposób że można wrócić do tego węzła, z którego zaczyna się ta "dróżka". To może być też rekurencyjna relacja dotycząca tego samego węzła, która pozwala na "wykonanie okrążenia" od tego samego węzła do tego samego węzła, już tak pisząc kolokwialnie (na graficznym przedstawieniu można to rozpoznać po okrężnej strzałce wychodzącej z węzła i wskazującej na ten sam węzeł).

Drugie ograniczenie nałożone na algorytm Dijkstry to dodatnie wartości wag krawędzi. Jeżeli program gdziekolwiek trafi na krawędź o ujemnej wadze, to się "wykopyrtnie" i pojawią się bzdury na wyjściu. Jeżeli tak bardzo Wam będzie zależało na zachowaniu wag ujemnych, to czeka Was przesiadka na algorytm Bellmana-Forda (odmiana algorytmu Dijkstry funkcjonująca prawidłowo na krawędziach o wartościach ujemnych).

Aby zrozumieć DLACZEGO graf musi przestrzegać tych ograniczeń, zapraszam do dalszej części ukazującej sposób działania krok po kroku…

JAK DZIAŁA ALGORYTM DIJKSTRY, ŻE POTRAFI ZIDENTYFIKOWAĆ ŚCIEŻKĘ?

Opowieść zaczyna się tak samo. Mamy jakiś tam graf:

Rysunek graficzny prezentujący graf ważony na potrzeby eksperymentu.

i chcemy przedostać się przez węzły od startu do mety. Co się będzie działo tym razem?

Algorytm Dijkstry wykorzystuje dwie tabelki. Jedna określa koszty dotarcia do danego węzła, a druga reprezentuje "rodziców" wszystkich węzłów poza startem i to przyda się do ustalenia drogi od węzła startowego do końcowego. Przyjrzyjmy się inicjalizacji tych dwóch tabelek.

TABELA KOSZTÓW

Koszty krawędzi to wartości liczbowe określające pewien wydatek ile czasu / energii / pieniędzy trzeba przeznaczyć na dotarcie do danego węzła. My na samym początku znamy koszty dotarcia do tych węzłów, które są w bezpośredniej relacji z naszym punktem startowym. Przy całej reszcie nie wiadomo ile kosztów trzeba ponieść, zatem umownie określamy je znakiem nieskończoności. Na wstępie, tabelka kosztów dotarcia do poszczególnych węzłów będzie wyglądała tak:

Prześledźcie to na spokojnie i spróbujcie już teraz rozkminić jaka struktura danych będzie pasowała do przechowania tych informacji ;).

TABELA RODZICÓW

Przez "rodzica" należy rozumieć węzeł od którego można dojść do sąsiedniego węzła. Postępujemy bardzo podobnie co wyżej, z tym że po prawej stronie zamiast wartości liczbowych, wskazujemy na nazwę węzła będącego sąsiadem, a wszelkie nieznane nam informacje oznaczamy znakiem zapytania:

Po opracowaniu tych tabelek, algorytm Dijkstry rozpoczyna swoje działania!

SELEKCJA WĘZŁÓW

Uwaga! W tej części będę używał kolorków, aby ułatwić zrozumienie tematu, bo potrafi zrobić mętlik w głowie ;)!

Patrząc na rysunek grafu powyżej, widzimy że punkt startowy łączy węzeł A i węzeł B. Program każdorazowo wybiera ten węzeł, który nie został jeszcze zbadany i koszt dotarcia do niego jest najmniejszy, więc wpierw bierze pod uwagę węzeł A i bada koszty wszystkich jego sąsiadów. Dla każdego węzła sąsiedniego, oblicza sumę kosztu dotarcia do węzła A i kosztu jego sąsiada. Jeżeli okaże się, że ta suma jest mniejsza od kosztu dotarcia do sąsiada odnotowanego w tabelce, to aktualizuje wpis w tabelce kosztów i rodziców. Do tabeli kosztów przypisuje tańszy koszt dotarcia do węzła sąsiedniego, a do tabeli rodziców przypisuje sąsiadowi rodzica (węzeł A). Algorytm wykonuje to samo dla każdego sąsiada, aż do "wyczerpania zapasów".

Kiedy wszyscy sąsiedzi zostaną rozpatrzeni, to węzeł A (węzeł, który został wybrany na samym początku) zostaje oznaczony jako "zbadany", a program wybiera kolejny węzeł o najmniejszym koszcie. Kiedy nie ma kogo już wybrać, działanie zostaje zakończone. Potem wystarczy sobie sięgnąć do tabeli rodziców i na jej podstawie zobaczyć jak się dostać od węzła startowego do końcowego. Te informacje wystarczą w zupełności, żeby "narysować" drogę. Tak właśnie funkcjonuje algorytm Dijkstry!

INTERESUJE MNIE ZŁOŻONOŚĆ OBLICZENIOWA

Ja myślę. Podsumujmy. Mamy graf, mamy węzły i mamy krawędzie. Podczas każdej pojedynczej iteracji wykreślamy węzeł do zbadania raz po raz. Dla każdego węzła penetrujemy wszystkich sąsiadów, czyli to będzie iloczyn. Jaki wniosek?

O(log|V|*|V| + |E|), gdzie V = zbiór wierzchołków, E = zbiór krawędzi

Tyle wyjdzie w najgorszym przypadku. Wcale to nie znaczy, że tak będzie zawsze, bo algorytm może natrafić na docelowy węzeł zanim spenetruje cały graf od stóp do głów.

Warto nadmienić, że to nie jest sztywno ustalona notacja dużego O algorytmu Dijkstry samego w sobie! To jest złożoność obliczeniowa implementacji jaką demonstruję poniżej. Przy użyciu pewnych trików i modyfikacji (np. kopca Fibonacciego), można zredukować wzrost obliczeń do jeszcze lepszych rezultatów. Więc tak naprawdę odpowiedź na to pytanie brzmi "to zależy jak to zaprogramujesz".

KOD ŹRÓDŁOWY

Aż doszliśmy do sedna sprawy i prawdopodobnie najbardziej interesującego podpunktu moich artykułów jakim jest patent podany na tacy. Częstujcie się językiem Java ;):

KLASA "MAIN"

public class Main {
	public static void main(String[] args) {
		new DijkstrasAlgorithm();
	}
}

KLASA "NODE"

import java. io.PrintStream;
import java. util.LinkedHashMap;

public class Node {
	private final String name;
	private final LinkedHashMap<Node, Integer> neighbours = new LinkedHashMap<>();

	private boolean visited;

	public Node(String name) {
		this.name = name;
	}

	@Override
	public int hashCode() {
		return name.hashCode();
	}

	@Override
	public boolean equals(Object o) {
		if(getClass() != o.getClass()) {
			return false;
		}

		Node n = (Node)o;

		return getName().equals(n.getName());
	}

	public void printDetails() {
		PrintStream ps = System.out;

		ps.println(name);
		getNeighbours().forEach((k, v) -> ps.println("\t" + k.getName()));
	}

	public void addNeighbour(Node node, int cost) {
		neighbours.put(node, cost);
	}

	public void setAsVisited() {
		visited = true;
	}

	public String getName() {
		return name;
	}

	public LinkedHashMap<Node, Integer> getNeighbours() {
		return neighbours;
	}

	public boolean isVisited() {
		return visited;
	}
}

KLASA "GRAPH"

import java. util.Arrays;
import java. util.LinkedHashSet;

public class Graph extends LinkedHashSet<Node> {
	private final Node nodeA = new Node("A");
	private final Node nodeB = new Node("B");
	private final Node nodeC = new Node("C");
	private final Node nodeD = new Node("D");
	private final Node nodeE = new Node("E");
	private final Node targetNode = new Node("META");

	public Graph(Node startNode) {
		addAll(Arrays.asList(startNode, nodeA, nodeB, nodeC, nodeD, nodeE, targetNode));
		setNeighbours(startNode);
	}

	public Node nodeByName(String key) {
		for (Node n : this) {
			if(n.getName().equals(key)) {
				return n;
			}
		}

		return new Node("NULL");
	}

	private void setNeighbours(Node startNode) {
		startNode.addNeighbour(nodeA, 3);
		startNode.addNeighbour(nodeB, 4);

		nodeA.addNeighbour(nodeC, 1);
		nodeA.addNeighbour(nodeD, 5);

		nodeB.addNeighbour(nodeE, 2);

		nodeC.addNeighbour(nodeD, 3);

		nodeD.addNeighbour(targetNode, 2);

		nodeE.addNeighbour(nodeD, 2);
		nodeE.addNeighbour(targetNode, 6);
	}
}

KLASA "TABLE"

import java. util.LinkedHashMap;

public abstract class Table<T> extends LinkedHashMap<String, T> {
	public final void putValues(Graph graph, Node startNode) {
		for (Node n : graph) {
			if(!n.getName().equals(startNode.getName())) {
				put(n.getName(), nodeValue(startNode, n));
			}
		}

		System.out.println(this);
	}

	public abstract T nodeValue(Node startNode, Node neighbour);
}

KLASA "COSTSTABLE"

import java. util.Map;

public class CostsTable extends Table<Integer> {
	@Override
	public Integer nodeValue(Node startNode, Node neighbour) {
		return startNode.getNeighbours().getOrDefault(neighbour, Integer.MAX_VALUE);
	}

	public Node lowestCostNode(Graph graph) {
		int lowestCost = Integer.MAX_VALUE;
		Node lowestCostNode = null;

		for (Map.Entry<String, Integer> entry : entrySet()) {
			int cost = entry.getValue();
			String key = entry.getKey();
			Node node = graph.nodeByName(key);

			if(cost < lowestCost && !node.isVisited()) {
				lowestCost = cost;
				lowestCostNode = node;
			}
		}

		return lowestCostNode;
	}
}

KLASA "PARENTSTABLE"

public class ParentsTable extends Table<String> {
	@Override
	public String nodeValue(Node startNode, Node neighbour) {
		return startNode.getNeighbours().containsKey(neighbour) ? startNode.getName() : null;
	}
}

KLASA "DIJKSTRASALGORITHM"

import java.io.PrintStream;
import java.util.*;

public class DijkstrasAlgorithm {
	private final Node startNode = new Node("START");
	private final Graph graph = new Graph(startNode);
	private final CostsTable costs = new CostsTable();
	private final ParentsTable parents = new ParentsTable();
	private final PrintStream printStream = System.out;

	public DijkstrasAlgorithm() {
		graph.forEach(Node::printDetails);
		costs.putValues(graph, startNode);
		parents.putValues(graph, startNode);
		findPath();
		printStream.println(costs);
		printStream.println(parents);
	}

	private void findPath() {
		Node parentNode;

		while ((parentNode = costs.lowestCostNode(graph)) != null) {
			int parentNodeCostFromTable = costs.get(parentNode.getName());
			LinkedHashMap<Node, Integer> neighbours = parentNode.getNeighbours();

			printStream.println("Obecny węzeł: " + parentNode.getName());
			printStream.println("======");

			for (Map.Entry<Node, Integer> entry : neighbours.entrySet()) {
				Node neighbourNode = entry.getKey();
				int edgeCost = entry.getValue();
				int totalCostFromGraphEdges = parentNodeCostFromTable + edgeCost;
				String neighbourNodeName = neighbourNode.getName();
				int neighbourCostFromTable = costs.get(neighbourNodeName);

				printStream.println("Obecny sąsiad: " + neighbourNodeName);
				printStream.println("Obecny koszt: " + neighbourCostFromTable);
				printStream.println("Koszt: " + parentNodeCostFromTable);
				printStream.println("Koszt sąsiada: " + edgeCost);
				printStream.println("Całkowity koszt: " + totalCostFromGraphEdges);
				printStream.println("======");

				if(neighbourCostFromTable > totalCostFromGraphEdges) {
					costs.put(neighbourNodeName, totalCostFromGraphEdges);
					parents.put(neighbourNodeName, parentNode.getName());
				}
			}

			parentNode.setAsVisited();
		}
	}
}

Uprzedzałem, że artykuł będzie o wiele obszerniejszy ;)! Algorytm Dijkstry wymagał ode mnie rozpisania na wielkiej kartce A4, abym pojął jakim cudem to działa. Kod źródłowy został napisany przy użyciu bardziej złożonych technik, więc postaram się wszystko wytłumaczyć ze szczególną starannością.

Popatrz na klasę "Node". To jest implementacja dla obiektów węzłów grafu. Posiada trzy dane składowe: etykietkę w charakterze łańcucha znaków, wartość boolowską kontrolującą stan "sprawdzonego" węzła oraz co najważniejsze, tablicę asocjacyjną dla węzłów sąsiednich. W dużym skrócie: słownik to kolekcja dla przechowywania par klucz-wartość. Odsyłam do odrębnego artykułu po więcej. Kluczem jest referencja do danego węzła, a wartością będzie koszt (czy też waga) dotarcia do tego węzła. Musieliśmy to zaprogramować w taki sposób, gdyż ważone są nie same węzły, tylko przejścia między nimi czyli relacje. Co zaś się tyczy metod - konstruktor wymaga podania nazwy węzła, przesłonięcia metod "hashCode" i "equals" dla ustalenia kryterium unikatowości są obecne, a reszta to tylko wypisywanie na terminal szczegółów o węźle i jego sąsiadach, dodawanie sąsiada do słownika i na samym końcu same akcesory oraz mutatory ("get" i "set").

Kolejna klasa, która jest w kolejności jako następna, to implementacja obiektu grafu. Wewnątrz niej wprowadziłem instancje naszych węzłów oraz dodanie powiązań między nimi przydzielając koszty zgodnie z rysunkiem. Dla odseparowania rodzajów instrukcji, dodałem metodę wyszukującą węzeł o podanej etykiecie i nałożyłem zabezpieczenie przed zwracaniem wartości "null", aby metoda zwracała węzeł "śmieciowy". Węzeł startowy przyjmowany jest pobierany z zewnątrz jako parametr, gdyż referencja jest potrzebna w klasie przeprowadzającej sam algorytm Dijkstry.

Lećmy dalej, bo najfajniejsze dopiero nadchodzi! Klasa "Table" może wyglądać na najbardziej skomplikowaną z powodu wprowadzenia typu ogólnego. Te tabelki są do siebie tak podobne, że nie mogłem się powstrzymać i skorzystałem z typów generycznych, które zostały wykorzystane w klasach potomnych. Tabelka dziedziczy od słownika, ponieważ z uwagi na to, że obie tabelki mają tylko dwie kolumny, to dlaczego by nie użyć ponownie tej samej struktury danych, która pasuje jak ulał ;)? W środku "Table" znajdujemy jedną metodę finalną oraz jedną abstrakcyjną, która będzie przesłaniania w obu klasach potomnych (dla tabeli kosztów i tabeli rodziców). Metoda finalna z implementacją wprowadza wartości początkowe wszystkich par klucz-wartość czyt. węzeł i typ ogólny, który będzie podstawiony w klasach potomnych (robimy tak, ponieważ koszty reprezentują liczbę całkowitą, a rodzice to będą nazwy węzłów jako łańcuchy znaków). Wewnątrz pętli rozszerzonej "for-each", umieszczamy pary jeżeli węzeł jest inny niż startowy. Za klucz podstawiamy obiekt węzła, a wartość...zależy od typu i implementacji jaka zostanie zdefiniowana w klasie potomnej.

Schodząc niżej, trafiamy na klasę potomną klasy "Table" dla tabeli kosztów. Co tam widzicie? Określenie typu konkretnego dla naszego nieznanego "T" (tu jest "Integer", czyli druga kolumna będzie reprezentować liczby całkowite), a wewnątrz przesłaniamy metodę "nodeValue" podając już typ właściwy oraz definicję kryterium zależności zwracanej wartości. "getOrDefault" wykonuje jedną z dwóch rzeczy: zwraca liczbę całkowitą kosztu w przypadku znalezienia węzła o podanej referencji albo zwraca nieskończoność w przypadku nieznalezienia węzła. Ponieważ zakres wszystkich rodzajów zmiennych jest ograniczony (bo wszystko jest SKOŃCZONYM ciągiem bitów), podstawiamy tak naprawdę "wielgachną" liczbę jaka kryje się za stałą "Integer.MAX_VALUE" (2³¹ - 1), czyli taka symulowana "nieskończoność". Druga metoda zwraca węzeł o najniższym koszcie, który nie został jeszcze zbadany. Po przejściu przez swoje wiersze i znalezieniu węzła o podanej nazwie ("graph.nodeByName(key)"), trzeba sprawdzić czy koszt jest mniejszy od aktualnego "rekordzisty" i czy węzeł nie został już wcześniej zbadany. Jeżeli oba warunki są spełnione, program "bierze" dany węzeł i traktuje go jako węzeł następny w kolejce do sprawdzenia. Gdy reszta niesprawdzonych węzłów nie będzie posiadała mniejszego kosztu, metoda zwraca aktualny węzeł i "dziękujemy za uwagę".

Druga klasa potomna klasy "Table" (przeznaczona dla "rodziców" węzłów) jest już nieco mniej enigmatyczna. Posiada tylko definicję metody abstrakcyjnej, a typ dla drugiej kolumny to łańcuch znaków (dla etykiet węzłów znalezionych jako "rodziców"). Implementacja metody "nodeValue" działa podobnie, z tym że w przypadku nieznalezienia węzła o podanej referencji, to zwraca "null", a jeśli znajdzie to przypisuje etykietkę punktu startowego. Pamiętajcie, że implementacja w obu klasach dotyczy konfiguracji tabelek na etapie POCZĄTKOWYM (patrz punkt "Tabela kosztów" i "Tabela rodziców")!

No i wreszcie, klasa wykonująca algorytm Dijkstry! Na samej górze mamy tworzenie szeregu instancji: dla węzła startowego, dla grafu, tabeli kosztów, tabeli rodziców oraz dla obiektu "PrintStream", aby nieco łatwiej wywoływać instrukcje wypisywania w terminalu. W konstruktorze występuje kilka wywołań różnych metod. Najpierw ujrzycie informacje o każdym z węzłów grafu razem z ich sąsiadami, następnie program zainicjuje obie tabelki w fazie początkowej, wywoła metodę przeprowadzającą operacje znajdowania ścieżki, a na samym końcu wypisze wyniki w postaci zawartości obu tabelek. "findPath" to "serce" niniejszego kodu! Widzimy po raz kolejny pętlę "while", w której sprawdzana jest referencja węzła czy jest kogo dalej sprawdzać (niezbadany węzeł dysponujący najniższym kosztem). Gdy taki się znajdzie, to pobierane są dwie wartości: koszt węzła pobierany z tabelki kosztów oraz słownik sąsiadów analizowanego węzła ("getNeighbours"). Potem mamy pętlę rozszerzoną penetrującą każdą parę klucz-wartość naszego słownika (musimy tutaj użyć mocno zagmatwanej składni z użyciem metody "entrySet") i pobieramy serię wartości. Pomijając serię instrukcji "println", istotną rolę gra tylko instrukcja warunkowa sprawdzająca czy koszt sąsiada odnotowany w tabelce kosztów przewyższa sumę kosztu węzła "wybranego" i kosztu krawędzi (przejścia od węzła "wybranego" do rozpatrywanego sąsiada) i jeżeli się okaże że tak, to program "wpisuje" do tablicy kosztów ten mniejszy koszt, a do tablicy rodziców węzeł "wybrany" jakim można przejść do węzła sąsiedniego. I tak w koło Macieju...

Nie złość się drogi Czytelniku, jeśli masz ogromne problemy ze zrozumieniem co się tu wyprawia. Jeżeli tak jest, to narysuj sobie na kartce wszystko krok po kroku i korzystaj z kolorowych mazaków. Wszystko stanie się jasne ;).

Dotarliśmy do mety (już bez "pathfindingu" ;)). Nie pytajcie ile czasu mi zajęło, żeby powstał ten artykuł.

PODOBNE ARTYKUŁY

• Przeszukiwanie wszerz. Teoria i kod źródłowy
• Przypadek optymistyczny, średni i najgorszy w algorytmice
• Sortowanie szybkie. Teoria i kod źródłowy