{"id":23037,"date":"2025-12-24T14:11:52","date_gmt":"2025-12-24T13:11:52","guid":{"rendered":"http:\/\/blog.wenzlaff.de\/?p=23037"},"modified":"2025-12-24T14:11:52","modified_gmt":"2025-12-24T13:11:52","slug":"vom-weihnachtsstau-zur-optimalroute-dijkstra-rettet-deinen-24-dezember-sortierschranke-sorting-barrier-durchbrochen","status":"publish","type":"post","link":"http:\/\/blog.wenzlaff.de\/?p=23037","title":{"rendered":"Vom Weihnachtsstau zur Optimalroute: Dijkstra rettet deinen 24. Dezember – Sortierschranke (sorting barrier) durchbrochen"},"content":{"rendered":"

Der Dijkstra-Algorithmus<\/a> kann das K\u00f6nigsberger Br\u00fcckenproblem nicht l\u00f6sen<\/a>. Aber die Berechnung k\u00fcrzester Pfade in gewichteten Graphen ist durchaus interessant \u2013 zum Beispiel, wenn man wissen m\u00f6chte, wie man von Frankfurt nach M\u00fcnchen die k\u00fcrzeste Strecke findet.<\/p>\n

\"Schneller<\/p>\n

Der Dijkstra-Algorithmus dient der Berechnung des k\u00fcrzesten Pfads in gewichteten Graphen mit nicht-negativen Kantenl\u00e4ngen. <\/p>\n

Dazu schreiben wir ein Java Demo Programm:<\/p>\n

package de.wenzlaff.mathe.dijkstra;\r\n\r\nimport java.util.ArrayList;\r\nimport java.util.Collections;\r\nimport java.util.List;\r\nimport java.util.Map;\r\n\r\n\/**\r\n * Demo-Programm f\u00fcr den Dijkstra-Algorithmus (Java 21) mit deutschen St\u00e4dten\r\n * als Knoten und Entfernungen in Kilometern.\r\n *\r\n * Der Graph ist ungerichtet und besitzt nur nicht-negative Kantengewichte.\r\n * \r\n * Der Algorithmus berechnet die k\u00fcrzesten Entfernungen von einem Startort\r\n * (hier: Frankfurt) zu allen anderen St\u00e4dten.\r\n * \r\n * @author Thomas Wenzlaff\r\n *\/\r\npublic class CityDijkstraDemo {\r\n\r\n    public static void main(String[] args) {\r\n\r\n\tGraph<String> graph = new Graph<>();\r\n\r\n\t\/\/ Knoten (St\u00e4dte)\r\n\tgraph.addNode(\"Frankfurt\");\r\n\tgraph.addNode(\"Mannheim\");\r\n\tgraph.addNode(\"Karlsruhe\");\r\n\tgraph.addNode(\"Augsburg\");\r\n\tgraph.addNode(\"M\u00fcnchen\");\r\n\tgraph.addNode(\"W\u00fcrzburg\");\r\n\tgraph.addNode(\"N\u00fcrnberg\");\r\n\tgraph.addNode(\"Stuttgart\");\r\n\tgraph.addNode(\"Erfurt\");\r\n\tgraph.addNode(\"Kassel\");\r\n\r\n\t\/\/ Ungerichtete Kanten mit Entfernungen in km\r\n\taddUndirectedEdge(graph, \"Frankfurt\", \"Mannheim\", 85);\r\n\taddUndirectedEdge(graph, \"Frankfurt\", \"W\u00fcrzburg\", 217);\r\n\taddUndirectedEdge(graph, \"Frankfurt\", \"Kassel\", 173);\r\n\r\n\taddUndirectedEdge(graph, \"Mannheim\", \"Karlsruhe\", 80);\r\n\r\n\taddUndirectedEdge(graph, \"Karlsruhe\", \"Augsburg\", 250);\r\n\taddUndirectedEdge(graph, \"Augsburg\", \"M\u00fcnchen\", 84);\r\n\r\n\taddUndirectedEdge(graph, \"W\u00fcrzburg\", \"N\u00fcrnberg\", 103);\r\n\taddUndirectedEdge(graph, \"W\u00fcrzburg\", \"Erfurt\", 186);\r\n\r\n\taddUndirectedEdge(graph, \"N\u00fcrnberg\", \"Stuttgart\", 183);\r\n\taddUndirectedEdge(graph, \"N\u00fcrnberg\", \"M\u00fcnchen\", 167);\r\n\r\n\taddUndirectedEdge(graph, \"Kassel\", \"M\u00fcnchen\", 502);\r\n\r\n\t\/\/ Startstadt f\u00fcr Dijkstra\r\n\tString start = \"Frankfurt\";\r\n\r\n\tMap<String, Integer> distanzen = graph.dijkstra(start);\r\n\tMap<String, String> vorgaenger = graph.getPredecessors();\r\n\r\n\tSystem.out.println(\"=== Dijkstra-Algorithmus Demo (Start: \" + start + \") ===\");\r\n\tSystem.out.printf(\"%-12s %-10s %s%n\", \"Stadt\", \"Distanz\", \"Pfad\");\r\n\tSystem.out.println(\"----------------------------------------------\");\r\n\r\n\tfor (String city : graph.getNodes()) {\r\n\t    String path = reconstructPath(vorgaenger, start, city);\r\n\t    int distance = distanzen.getOrDefault(city, Integer.MAX_VALUE);\r\n\t    String distStr = distance == Integer.MAX_VALUE ? \"\u221e\" : String.valueOf(distance);\r\n\t    System.out.printf(\"%-12s %-10s %s%n\", city, distStr, path);\r\n\t}\r\n    }\r\n\r\n    \/**\r\n     * F\u00fcgt eine ungerichtete Kante ein, indem zwei gerichtete Kanten mit\r\n     * identischem Gewicht erzeugt werden.\r\n     *\/\r\n    private static void addUndirectedEdge(Graph<String> graph, String a, String b, int distance) {\r\n\tgraph.addEdge(a, b, distance);\r\n\tgraph.addEdge(b, a, distance);\r\n    }\r\n\r\n    \/**\r\n     * Rekonstruiert den Pfad von start nach target anhand der Vorg\u00e4nger-Map.\r\n     *\/\r\n    private static String reconstructPath(Map<String, String> predecessors, String start, String target) {\r\n\tif (start.equals(target)) {\r\n\t    return start;\r\n\t}\r\n\tif (!predecessors.containsKey(target)) {\r\n\t    return \"nicht erreichbar\";\r\n\t}\r\n\r\n\tList<String> path = new ArrayList<>();\r\n\tString current = target;\r\n\twhile (current != null) {\r\n\t    path.add(current);\r\n\t    if (current.equals(start))\r\n\t\tbreak;\r\n\t    current = predecessors.get(current);\r\n\t}\r\n\tCollections.reverse(path);\r\n\treturn String.join(\" -> \", path);\r\n    }\r\n}\r\n<\/pre>\n
Und eine Graph Klasse:<\/p>\n
package de.wenzlaff.mathe.dijkstra;\r\n\r\nimport java.util.Comparator;\r\nimport java.util.HashMap;\r\nimport java.util.HashSet;\r\nimport java.util.Map;\r\nimport java.util.PriorityQueue;\r\nimport java.util.Set;\r\n\r\n\/**\r\n * Einfache gewichtete Graph-Implementierung f\u00fcr Dijkstra.\r\n *\r\n * @param <T> Typ der Knotenschl\u00fcssel (z.B. String)\r\n * \r\n * @author Thomas Wenzlaff\r\n *\/\r\nclass Graph<T> {\r\n\r\n    private final Map<T, Map<T, Integer>> adjacency = new HashMap<>();\r\n\r\n    private Map<T, T> predecessors = new HashMap<>();\r\n\r\n    public void addNode(T node) {\r\n\tadjacency.putIfAbsent(node, new HashMap<>());\r\n    }\r\n\r\n    \/**\r\n     * F\u00fcgt eine gerichtete Kante mit ganzzahligem Gewicht hinzu.\r\n     *\/\r\n    public void addEdge(T source, T target, int weight) {\r\n\tif (weight < 0) {\r\n\t    throw new IllegalArgumentException(\"Negative Gewichte sind nicht erlaubt\");\r\n\t}\r\n\taddNode(source);\r\n\taddNode(target);\r\n\tadjacency.get(source).put(target, weight);\r\n    }\r\n\r\n    \/**\r\n     * Dijkstra-Algorithmus: berechnet k\u00fcrzeste Entfernungen vom Startknoten.\r\n     *\r\n     * @param start Startknoten\r\n     * @return Map mit minimalen Distanzen zu allen Knoten\r\n     *\/\r\n    public Map<T, Integer> dijkstra(T start) {\r\n\tMap<T, Integer> dist = new HashMap<>();\r\n\tpredecessors = new HashMap<>();\r\n\tSet<T> visited = new HashSet<>();\r\n\r\n\tfor (T node : adjacency.keySet()) {\r\n\t    dist.put(node, Integer.MAX_VALUE);\r\n\t}\r\n\tdist.put(start, 0);\r\n\r\n\trecord Entry<T>(T node, int distance) {\r\n\t}\r\n\tPriorityQueue<Entry<T>> pq = new PriorityQueue<>(Comparator.comparingInt(Entry::distance));\r\n\r\n\tpq.add(new Entry<>(start, 0));\r\n\r\n\twhile (!pq.isEmpty()) {\r\n\t    Entry<T> currentEntry = pq.poll();\r\n\t    T u = currentEntry.node;\r\n\r\n\t    if (!visited.add(u)) {\r\n\t\tcontinue;\r\n\t    }\r\n\r\n\t    int du = dist.get(u);\r\n\t    if (du == Integer.MAX_VALUE) {\r\n\t\tcontinue;\r\n\t    }\r\n\r\n\t    for (Map.Entry<T, Integer> edge : adjacency.get(u).entrySet()) {\r\n\t\tT v = edge.getKey();\r\n\t\tint weight = edge.getValue();\r\n\t\tint alt = du + weight;\r\n\t\tif (alt < dist.getOrDefault(v, Integer.MAX_VALUE)) {\r\n\t\t    dist.put(v, alt);\r\n\t\t    predecessors.put(v, u);\r\n\t\t    pq.add(new Entry<>(v, alt));\r\n\t\t}\r\n\t    }\r\n\t}\r\n\r\n\treturn dist;\r\n    }\r\n\r\n    public Set<T> getNodes() {\r\n\treturn adjacency.keySet();\r\n    }\r\n\r\n    public Map<T, String> getStringPredecessors() {\r\n\tMap<T, String> map = new HashMap<>();\r\n\tfor (Map.Entry<T, T> e : predecessors.entrySet()) {\r\n\t    map.put(e.getKey(), e.getValue().toString());\r\n\t}\r\n\treturn map;\r\n    }\r\n\r\n    public Map<T, T> getPredecessors() {\r\n\treturn predecessors;\r\n    }\r\n}\r\n<\/pre>\n
Das Ergebnis nach der Ausf\u00fchrung in Eclipse:<\/p>\n
\"\"<\/p>\n
Der Code ist auch in meinem GitLab-Repo<\/a> zu finden.<\/p>\n
Jahrelang hat man gedacht, das der Dijkstra-Algorithmus die schnellste L\u00f6sung des Problems ist. Das mathematische Tempolimit<\/strong>, in den Quellen<\/a> als Sortierschranke<\/strong> (sorting barrier) bezeichnet, galt seit dem Jahr 1984. <\/p>\n
In diesem Jahr gelang es dem Informatiker Robert Tarjan zusammen mit einem Kollegen, den klassischen Dijkstra-Algorithmus so weit zu optimieren, dass er genau an diese theoretische Grenze stie\u00df. Vor kurzem<\/a> hat man dann eine bahnbrechende Entdeckung gemacht, es geht doch schneller<\/strong> wie in A New Algorithm Makes It Faster to Find the Shortest Paths<\/a> gezeigt.<\/p>\n
Dieser Artikel<\/a> beschreibt einen bedeutenden Durchbruch in der Informatik, bei dem Forscher eine vierzig Jahre alte Geschwindigkeitsbarriere f\u00fcr K\u00fcrzeste-Wege-Algorithmen durchbrochen haben. W\u00e4hrend klassische Methoden wie der Dijkstra-Algorithmus durch die notwendige Sortierung von Distanzen begrenzt waren, nutzt das neue Team um Ran Duan innovative Gruppierungstechniken. Durch die gezielte Identifizierung einflussreicher Knotenpunkte umgeht das Verfahren die Sortierschranke und arbeitet effizienter auf komplexen Graphen. <\/p>\n
Zusammenfassend l\u00e4sst sich sagen: W\u00e4hrend der aktuelle messbare Geschwindigkeitsvorteil gegen\u00fcber der optimierten Dijkstra-Variante eher klein ist, ist der theoretische Unterschied gigantisch, da er beweist, dass das bisherige mathematische Gesetz zur H\u00f6chstgeschwindigkeit f\u00fcr diese Art von Problemen nicht mehr gilt.<\/p>\n
Man kann sich das wie das Durchbrechen der Schallmauer vorstellen: Es geht nicht nur darum, ein paar Stundenkilometer schneller zu sein als das bisher schnellste Flugzeug, sondern darum, eine physikalische Grenze \u00fcberwunden zu haben, die zuvor als absolut galt, und damit den Weg f\u00fcr eine v\u00f6llig neue Generation von Triebwerken zu ebnen. Ich bin gespannt was da noch kommt.<\/p>\n","protected":false},"excerpt":{"rendered":"
Der Dijkstra-Algorithmus kann das K\u00f6nigsberger Br\u00fcckenproblem nicht l\u00f6sen. Aber die Berechnung k\u00fcrzester Pfade in gewichteten Graphen ist durchaus interessant \u2013 zum Beispiel, wenn man wissen m\u00f6chte, wie man von Frankfurt nach M\u00fcnchen die k\u00fcrzeste Strecke findet. Der Dijkstra-Algorithmus dient der Berechnung des k\u00fcrzesten Pfads in gewichteten Graphen mit nicht-negativen Kantenl\u00e4ngen.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[220,5,3897,6180,79],"tags":[6279,1632,2178,6281,5850,2079,6280,6282,6283],"class_list":["post-23037","post","type-post","status-publish","format-standard","hentry","category-anleitung","category-java","category-java-programmierung","category-java-21","category-programmierung","tag-dijkstra-algorithmus","tag-graph","tag-java","tag-kuerzester-weg","tag-mathe","tag-navi","tag-pfad","tag-sortierschranke","tag-sorting-barrier"],"_links":{"self":[{"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=\/wp\/v2\/posts\/23037","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=23037"}],"version-history":[{"count":0,"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=\/wp\/v2\/posts\/23037\/revisions"}],"wp:attachment":[{"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=23037"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=23037"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.wenzlaff.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=23037"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}