Kürzester-Wege-Rechner (Dijkstra Schritt für Schritt)

Kürzester-Wege-Rechner (Dijkstra Schritt für Schritt) | Kostenloses Online-Tool | Elysia Tools

Leitfaden zur Tool-Nutzung

Erfahren Sie, wann dieses Tool passt, was es unterstützt und wie Nutzer es anwenden.

Wichtige Fakten

Kategorie: Math & Numbers
Eingabetypen: textarea, text, checkbox, number
Ausgabetyp: text
Sample-Abdeckung: 4
API bereit: Ja

Überblick

Der Kürzester-Wege-Rechner ermittelt den optimalen Pfad in gewichteten Graphen mithilfe des Dijkstra-Algorithmus und liefert ein detailliertes Protokoll aller Einzelschritte. Sie geben bis zu 30 Kanten mit ihren positiven Gewichten sowie Start- und Zielknoten ein, um den gesamten Verlauf der Knotenfixierungen und Kanten-Relaxationen wie in einer Lehrbuch-Tabelle nachzuvollziehen.

Wann verwenden

Beim Lösen oder Korrigieren von Übungsaufgaben zur Graphentheorie und diskreten Mathematik.
Zur Verifikation von manuell durchgeführten Dijkstra-Tabellen inklusive aller Relaxationsschritte.
Zur Analyse von einfachen gerichteten oder ungerichteten Routing- und Transportnetzwerken.

So funktioniert es

1Tragen Sie die Kanten des Graphen zeilenweise im Format 'KnotenA KnotenB Gewicht' ein (1–8 Zeichen pro Knotenname, nicht-negative Gewichte).
2Legen Sie den Start- und Zielknoten fest und wählen Sie optional, ob Kanten als gerichtet interpretiert werden sollen.
3Stellen Sie die gewünschte Anzahl an Dezimalstellen für die Distanzausgabe ein.
4Der Algorithmus berechnet schrittweise die kürzeste Distanz, löst Gleichstände lexikographisch auf und gibt den exakten Pfad sowie das Iterationsprotokoll aus.

Anwendungsfälle

Nachvollziehen von Dijkstra-Iterationen und Distanztabellen für Klausurvorbereitungen.
Überprüfung von Routing-Entscheidungen in kleinen gerichteten Netzwerk-Topologien.
Erstellung von verifizierten Musterlösungen für Dozenten und Tutoren der Informatik.

Beispiele

1. Ungerichtetes Standardnetzwerk A nach F

Informatikstudent

Hintergrund

Für ein Übungsblatt in Algorithmen und Datenstrukturen muss der Dijkstra-Ablauf tabellarisch Schritt für Schritt dokumentiert werden.

Aufgabe

Manuelles Nachrechnen ist fehleranfällig bei zwischenzeitlichen Distanzverbesserungen (Relaxation von D über E).

Verwendung

Kantenliste eingeben, Startknoten 'A' und Zielknoten 'F' setzen, Kanten ungerichtet lassen und Berechnung ausführen.

edges: A B 4\nA C 2\nB C 5\nB D 10\nC E 3\nD E 4\nD F 11\nE F 8, source: A, target: F, directed: false, decimalPlaces: 2

Ergebnis

Gesamtdistanz 13 über die Route A → C → E → F mit lückenlosem Protokoll aller Fixierungen und Tabellenupdates.

2. Gerichteter Graph mit Abkürzung S nach C

Netzwerktechnik-Dozent

Hintergrund

Ein Dozent erstellt eine Übungsaufgabe, bei der eine scheinbar längere Zwischenroute gerichtete Kanten effizienter nutzt.

Aufgabe

Erstellen einer fehlerfreien Musterlösung für die schrittweise Relaxation von Knoten S zu C.

Verwendung

FAQ

Unterstützt das Tool negative Kantengewichte?

Nein, negative Kantengewichte werden abgewiesen, da der Standard-Dijkstra-Algorithmus für nicht-negative Gewichte ausgelegt ist.

Wie werden Gleichstände zwischen Knoten mit gleicher Distanz aufgelöst?

Gleichstände werden deterministisch über den lexikographisch kleinsten Knotennamen aufgelöst, passend zu gängigen Lehrbuch-Standards.

Was passiert, wenn der Zielknoten nicht erreichbar ist?

Das Tool meldet das Ziel als unerreichbar, sobald alle erreichbaren Knoten fixiert wurden und keine Verbindung zum Ziel existiert.

Können gerichtete und ungerichtete Graphen berechnet werden?

Ja, standardmäßig werden Kanten als ungerichtet gewertet; über die Option 'Kanten als gerichtet behandeln' gilt die Richtung von Knoten 1 nach Knoten 2.

Wie viele Kanten können maximal eingegeben werden?

Das Werkzeug ist für die schrittweise Analyse von kleineren Graphen mit 1 bis 30 Kanten optimiert.

edges: S A 2\nS B 4\nA B 1\nA C 7\nB C 3, source: S, target: C, directed: true, decimalPlaces: 2

Dieses Tool ausführen

Beispiele zu diesem Tool

Mit verwandten Tools und Themen fortfahren

Erfahren Sie, wann dieses Tool passt, was es unterstützt und wie Nutzer es anwenden.

Wichtige Fakten

Überblick

Wann verwenden

So funktioniert es

Anwendungsfälle

Beispiele

1. Ungerichtetes Standardnetzwerk A nach F

2. Gerichteter Graph mit Abkürzung S nach C

FAQ

Pfad-Analyzer-Beispiele

Importpfad-Beispiele

ELK Stack Log-Analyse Beispiele

MP3 Audio-Beispiele ohne Urheberrechte

Audio-zu-Text Transkriptor (KI)

Eingerückte Liste zu ASCII-Baum

Kopfüber-Text

Zuordnungsproblem-Löser (ungarischer Algorithmus)