Die Quellcodes zum Artikel findest du in meinem GitHub-Repository<\/a>.<\/p>\n\n\n\n Ein Shortest-Path<\/em>-Algorithmus l\u00f6st das Problem der Suche nach dem k\u00fcrzesten Weg zwischen zwei Punkten in einem Graph (z. B. auf einer Stra\u00dfenkarte). Der Begriff \"kurz\" meint damit nicht unbedingt die physische Distanz<\/em>. Es kann sich dabei beispielsweise auch um Zeit<\/em> (Autobahnen werden bevorzugt) oder Kosten<\/em> (Maut-Stra\u00dfen werden gemieden) oder eine Kombination aus mehreren Faktoren handeln.<\/p>\n\n\n\n Graphen k\u00f6nnen sehr komplex sein und Millionen von Knoten und Kanten enthalten (beispielsweise in einer Videospiel-Welt, in der sich hunderte oder tausende Charaktere frei bewegen k\u00f6nnen), so dass die Suche nach dem optimalen Weg sehr aufw\u00e4ndig w\u00e4re.<\/p>\n\n\n\n F\u00fcr bestimmte Anwendungsgebiete gen\u00fcgt es einen einigerma\u00dfen<\/em> kurzen (oder sogar irgendeinen<\/em>) Weg zu finden. Hier spricht man dann allgemein von Pathfinding<\/em>.<\/p>\n\n\n\n Die bekanntesten Shortest-Path-Algorithmen sind:<\/p>\n\n\n\n Auf zweidimensionalen, in Kacheln unterteilte Karten, wie sie in fr\u00fchen Computerspielen \u00fcblich waren, kann auch eine Form der Breitensuche \u2013 bekannt als Lee-Algorithmus<\/a> \u2013 durchgef\u00fchrt werden.<\/p>\n\n\n\n Eine optimierte Variante davon erl\u00e4utere ich im verbleibenden Teil dieses Artikels an einem Beispiel mit Animationen und Java-Quellcode.<\/p>\n\n\n\n Mein pers\u00f6nliches Lieblingsbeispiel f\u00fcr die L\u00f6sung des Shortest-Path-Problems ist das Spiel \"FatCat\" auf dem HP-85<\/a>, einem Computer aus den 1980er Jahren, mit dem ich als Kind bei meinem Onkel experimentieren durfte.<\/p>\n\n\nShortest Path oder Pathfinding?<\/h2>\n\n\n\n
Shortest-Path-Algorithmen<\/h2>\n\n\n\n
\n
Labyrinth-Algorithmus: Wie findet man den k\u00fcrzesten Weg in einem Labyrinth?<\/h2>\n\n\n\n
![\"FatCat](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/fatcat-playing.gif\")