{"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-08-03T11:54:38","modified_gmt":"2026-08-03T09:54:38","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":"\n<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\n\n\n<figure class=\"wp-block-image aligncenter size-full is-resized\" style=\"width:300px;max-width:100%;margin-top:32px;margin-right:auto;margin-bottom:32px;margin-left:auto\"><img alt=\"Illustration zu \u201eSehr schnell stellt sich ein Problem: Wie kann man den k\u00fcrzesten Weg zwischen zwei Gipfeln bestimmen?\u201c\" decoding=\"async\" height=\"273\" loading=\"lazy\" src=\"https:\/\/liora.io\/app\/uploads\/sites\/8\/2022\/11\/pasted-image-0-6.webp\" style=\"width:300px;max-width:100%;height:auto\" width=\"300\"\/><\/figure>\n\n\n\n<p>Hier werden die St\u00e4dte A bis J durch die <strong>Eckpunkte<\/strong> des Graphen dargestellt.<\/p>\n\n\n\n<p>Sie 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.<\/p>\n\n\n\n<p>Hier kann jedes Gewicht als die Entfernung zwischen den beiden verbundenen St\u00e4dten betrachtet werden.<\/p>\n\n\n\n<p>Sehr schnell stellt sich ein Problem: Wie kann man den k\u00fcrzesten Weg zwischen zwei Gipfeln bestimmen?<\/p>\n\n\n\n<p>Hier kommt der Dijkstra-Algorithmus ins Spiel!<\/p>\n\n\n\n<p><strong>Wie funktioniert der Dijkstra-Algorithmus?<\/strong><\/p>\n\n\n\n<p>Angenommen, es wird versucht, den k\u00fcrzesten Weg von Stadt A nach Stadt J zu finden.<\/p>\n\n\n\n<p>W\u00e4hrend des gesamten Algorithmus werden wir den k\u00fcrzesten Weg von A zu jeder anderen Stadt in einer Tabelle speichern.<\/p>\n\n\n\n<p>Immer wieder wird der gleiche Vorgang wiederholt:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Du w\u00e4hlst den erreichbaren Gipfel mit der geringsten Entfernung als zu erforschenden Gipfel aus.<\/li>\n<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<li>Dies wird so lange wiederholt, bis man am Zielpunkt angekommen ist oder bis alle Gipfel erkundet wurden.<\/li>\n<\/ol>\n\n\n\n<p>Das ist alles ein bisschen vage&#8230;<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"wie-sieht-das-konkret-aus\">Wie sieht das konkret aus?<\/h2>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\" style=\"margin-top:32px;margin-bottom:32px\"><div class=\"wp-block-embed__wrapper\" style=\"position:relative;width:100%;padding-top:56.25%;overflow:hidden\"><iframe loading=\"lazy\" title=\"YouTube video L4bidK4cASM\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/L4bidK4cASM?rel=0\" style=\"position:absolute;inset:0;width:100%;height:100%;border:0\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/div><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"schlussfolgerung\">Schlussfolgerung<\/h3>\n\n\n\n<p>Die 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.<\/p>\n\n\n\n<p>Zum 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.<\/p>\n\n\n\n<div class=\"wp-block-buttons is-layout-flex wp-block-buttons-is-layout-flex is-content-justification-center wp-container-core-buttons-is-layout-5ee10de4\" style=\"margin-top:32px;margin-bottom:32px\"><div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/liora.io\/de\/weiterbildung\/data-ki\/data-scientist\">Entdecke die Ausbildung Data Scientist<\/a><\/div><\/div>\n\n\n\n<p>Diese 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!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"weiterfuhrende-informationen\">Weiterf\u00fchrende Informationen:<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<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<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<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>\n\n\n\n<p>Hat dir dieser Artikel gefallen? Unser <strong>Data Scientist-Kurs<\/strong> beinhaltet auch einen Kurs \u00fcber Graphentheorie. Warte nicht l\u00e4nger, sondern entdecke den Lehrplan!<\/p>\n\n\n\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":5,"href":"https:\/\/liora.io\/de\/wp-json\/wp\/v2\/posts\/165293\/revisions"}],"predecessor-version":[{"id":223331,"href":"https:\/\/liora.io\/de\/wp-json\/wp\/v2\/posts\/165293\/revisions\/223331"}],"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}]}}