{"id":165293,"date":"2026-01-28T16:20:55","date_gmt":"2026-01-28T15:20:55","guid":{"rendered":"https:\/\/liora.io\/de\/?p=165293"},"modified":"2026-02-06T04:24:37","modified_gmt":"2026-02-06T03:24:37","slug":"was-ist-der-dijkstra-algorithmus","status":"publish","type":"post","link":"https:\/\/liora.io\/de\/was-ist-der-dijkstra-algorithmus","title":{"rendered":"Dijkstra-Algorithmus: Wie findet man den k\u00fcrzesten Weg?"},"content":{"rendered":"<p><strong>Die Graphentheorie ist ein Zweig der Mathematik und Informatik, bei dem verschiedene Probleme aus dem wirklichen Leben in Form von Graphen modelliert werden. Eine der klassischsten Anwendungen ist die Modellierung eines Stra\u00dfennetzes zwischen verschiedenen St\u00e4dten. Eines der Hauptprobleme ist die Optimierung der Entfernungen zwischen zwei Punkten. Um die k\u00fcrzeste Strecke zu finden, wird oft der Dijkstra-Algorithmus verwendet. In diesem Artikel erf\u00e4hrst du mehr dar\u00fcber, wie er funktioniert:<\/strong><\/p>\n<img decoding=\"async\" width=\"300\" height=\"273\" src=\"https:\/\/liora.io\/app\/uploads\/sites\/8\/2022\/11\/pasted-image-0-6.webp\" alt=\"\" loading=\"lazy\">\n\nHier werden die St\u00e4dte A bis J durch die <strong>Eckpunkte<\/strong> des Graphen dargestellt.\n\nSie sind durch Stra\u00dfen verbunden, die den <strong>Kanten<\/strong> des Graphen entsprechen. Jeder Kante ist ein Wert zugeordnet, der als <strong>Gewicht bezeichnet wird<\/strong>. Sie entspricht normalerweise den Kosten oder der Entfernung.\n\nHier kann jedes Gewicht als die Entfernung zwischen den beiden verbundenen St\u00e4dten betrachtet werden.\n<h2 class=\"wp-block-heading\" id=\"h-sehr-schnell-stellt-sich-ein-problem-wie-kann-man-den-kurzesten-weg-zwischen-zwei-gipfeln-bestimmen\">Sehr schnell stellt sich ein Problem: Wie kann man den k\u00fcrzesten Weg zwischen zwei Gipfeln bestimmen?<\/h2>\nHier kommt der Dijkstra-Algorithmus ins Spiel!\n\n<strong>Wie funktioniert der Dijkstra-Algorithmus?<\/strong>\n\nAngenommen, es wird versucht, den k\u00fcrzesten Weg von Stadt A nach Stadt J zu finden.\n\nW\u00e4hrend des gesamten Algorithmus werden wir den k\u00fcrzesten Weg von A zu jeder anderen Stadt in einer Tabelle speichern.\n\nImmer wieder wird der gleiche Vorgang wiederholt:\n<ol>\n \t<li>Du w\u00e4hlst den erreichbaren Gipfel mit der geringsten Entfernung als zu erforschenden Gipfel aus.<\/li>\n \t<li>Von diesem Gipfel aus erforscht man seine Nachbarn und aktualisiert die Entfernungen f\u00fcr jeden. Du aktualisierst die Distanz nur, wenn sie kleiner ist als die, die du vorher hattest.<\/li>\n \t<li>Dies wird so lange wiederholt, bis man am Zielpunkt angekommen ist oder bis alle Gipfel erkundet wurden.<\/li>\n<\/ol>\nDas ist alles ein bisschen vage&#8230;\n<h2 class=\"wp-block-heading\" id=\"h-wie-sieht-das-konkret-aus\">Wie sieht das konkret aus?<\/h2>\n<iframe title=\"Animation Dijkstra Avec Tableau Prev 0005\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/L4bidK4cASM?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<h2 class=\"wp-block-heading\" id=\"h-schlussfolgerung\">Schlussfolgerung<\/h2>\nDie abschlie\u00dfende Tabelle gibt uns den Wert des k\u00fcrzesten Weges f\u00fcr jeden Eckpunkt des Graphen. Au\u00dferdem speichert sie den Ursprung des vorherigen Punktes, von dem aus der k\u00fcrzeste Weg ermittelt wurde.\n\nZum Beispiel sagt uns der Wert 403C f\u00fcr den Gipfel G, dass es 403 km dauert, um ihn zu erreichen, und dass dieser k\u00fcrzeste Weg direkt davor durch den Punkt C f\u00fchrt. Du kannst also einfach in der Tabelle nach oben scrollen, um den k\u00fcrzesten Weg f\u00fcr jeden beliebigen Gipfel zu erhalten.\n\nDiese Besonderheit erkl\u00e4rt <strong>den Vorteil des Dijkstra-Algorithmus<\/strong>: Mit nur einer Iteration erh\u00e4lt man den k\u00fcrzesten Weg f\u00fcr jeden Gipfel!\n<h2 class=\"wp-block-heading\" id=\"h-weiterfuhrende-informationen\">Weiterf\u00fchrende Informationen:<\/h2>\n<ul>\n \t<li>Es gibt viele andere Algorithmen, die das Problem des k\u00fcrzesten Weges l\u00f6sen. Man muss jedoch darauf achten, unter <strong>welchen Bedingungen<\/strong> diese verschiedenen Algorithmen <strong>angewendet werden<\/strong>. Der topologische Sortieralgorithmus zum Beispiel ist effizienter als der Dijkstra-Algorithmus, l\u00e4sst sich aber nur auf azyklische Graphen (ohne Schleifen) anwenden.<\/li>\n \t<li>Die <strong>Komplexit\u00e4t<\/strong> des Dijkstra-Algorithmus ist polynomial. Sei n die Anzahl der Eckpunkte und a die Anzahl der B\u00f6gen, sie ist im schlimmsten Fall in O(a+ nlog(n))<\/li>\n \t<li>Edsger Dijkstra entdeckte diesen Algorithmus innerhalb von 20 Minuten, als er in einem Stra\u00dfencaf\u00e9 nach dem besten Weg von Rotterdam nach Groningen suchte. Wie <strong>ein Kaffee viele Probleme l\u00f6sen kann<\/strong>.<\/li>\n<\/ul>\nHat dir dieser Artikel gefallen? Unser <strong>Data Scientist-Kurs<\/strong> beinhaltet auch einen Kurs \u00fcber Graphentheorie. Warte nicht l\u00e4nger, sondern entdecke den Lehrplan!\n\n\n<div class=\"wp-block-buttons is-layout-flex wp-block-buttons-is-layout-flex is-content-justification-center\"><div class=\"wp-block-button \"><a class=\"wp-block-button__link wp-element-button \" href=\"https:\/\/liora.io\/de\/weiterbildung-data-scientist\">Entdecke die Ausbildung Data Scientist<\/a><\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Die Graphentheorie ist ein Zweig der Mathematik und Informatik, bei dem verschiedene Probleme aus dem wirklichen Leben in Form von Graphen modelliert werden. Eine der klassischsten Anwendungen ist die Modellierung eines Stra\u00dfennetzes zwischen verschiedenen St\u00e4dten. Eines der Hauptprobleme ist die Optimierung der Entfernungen zwischen zwei Punkten. Um die k\u00fcrzeste Strecke zu finden, wird oft der Dijkstra-Algorithmus verwendet. In diesem Artikel erf\u00e4hrst du mehr dar\u00fcber, wie er funktioniert:<\/p>\n","protected":false},"author":47,"featured_media":165294,"comment_status":"open","ping_status":"open","sticky":false,"template":"elementor_theme","format":"standard","meta":{"_acf_changed":false,"editor_notices":[],"footnotes":""},"categories":[2476],"class_list":["post-165293","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-cloud-dev"],"acf":[],"_links":{"self":[{"href":"https:\/\/liora.io\/de\/wp-json\/wp\/v2\/posts\/165293","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/liora.io\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/liora.io\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/liora.io\/de\/wp-json\/wp\/v2\/users\/47"}],"replies":[{"embeddable":true,"href":"https:\/\/liora.io\/de\/wp-json\/wp\/v2\/comments?post=165293"}],"version-history":[{"count":3,"href":"https:\/\/liora.io\/de\/wp-json\/wp\/v2\/posts\/165293\/revisions"}],"predecessor-version":[{"id":216377,"href":"https:\/\/liora.io\/de\/wp-json\/wp\/v2\/posts\/165293\/revisions\/216377"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/liora.io\/de\/wp-json\/wp\/v2\/media\/165294"}],"wp:attachment":[{"href":"https:\/\/liora.io\/de\/wp-json\/wp\/v2\/media?parent=165293"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/liora.io\/de\/wp-json\/wp\/v2\/categories?post=165293"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}