Datei:Dijkstra-negative-edge-weights-error.svg
Größe der PNG-Vorschau dieser SVG-Datei: 400 × 240 Pixel. Weitere aus SVG automatisch erzeugte PNG-Grafiken in verschiedenen Auflösungen: 640 × 384 Pixel | 1.024 × 614 Pixel | 1.280 × 768 Pixel | 2.560 × 1.536 Pixel
Originaldatei (SVG-Datei, Basisgröße: 400 × 240 Pixel, Dateigröße: 2 KB)
Diese Datei und die Informationen unter dem roten Trennstrich werden aus dem zentralen Medienarchiv Wikimedia Commons eingebunden.
Beschreibung
| Beschreibung |
Deutsch: Beispiel, warum negative Kantengewichte nicht zulässig sind: Startend in Knoten eins, wird Dijkstra im ersten Schritt d(zwei)=1 und d(vier)=4 setzen, d(zwei) ist am kleinsten, folglich wird im nächsten Schritt d(drei)=2 gesetzt. d(drei) ist kleiner als d(vier), hat aber keine weiteren Nachbarn. Folglich wird Knoten vier als letztes betrachtet und damit niemals die negative Kante (4,3), da Dijkstra zuvor abbricht. English: Dijkstra's algorithm doesn't work with negative edge weights. For instance, consider the graph: Starting in vertex 1, Dijkstra's algorithm will choose the edge (1,2) setting dist(vertex 2)=1 and edge (1,4) setting dist(vertex 4)=4. dist(vertex 2) is smallest distance, so Dijkstra will choose edge (2,3) setting dist(vertex 3)=2. Smallest distance is dist(vertex 3). Because vertex 4 is the last one visited, it never finds the shortest path from 1 to 3, via 4, with total length 1. |
| Datum | |
| Quelle | Redrawn in SVG, original PNG Dijkstra negative edge weights error.png by Chin tin tin |
| Urheber | Stkl |
Diese Vektorgrafik wurde mit einem Texteditor erstellt. Die Validierung hat sie für syntaktisch korrekt befunden.
Lizenz
Diese Datei ist unter der Creative-Commons-Lizenz „Namensnennung – Weitergabe unter gleichen Bedingungen 3.0 nicht portiert“ lizenziert.
- Dieses Werk darf von dir
- verbreitet werden – vervielfältigt, verbreitet und öffentlich zugänglich gemacht werden
- neu zusammengestellt werden – abgewandelt und bearbeitet werden
- Zu den folgenden Bedingungen:
- Namensnennung – Du musst angemessene Urheber- und Rechteangaben machen, einen Link zur Lizenz beifügen und angeben, ob Änderungen vorgenommen wurden. Diese Angaben dürfen in jeder angemessenen Art und Weise gemacht werden, allerdings nicht so, dass der Eindruck entsteht, der Lizenzgeber unterstütze gerade dich oder deine Nutzung besonders.
- Weitergabe unter gleichen Bedingungen – Wenn du das Material wiedermischst, transformierst oder darauf aufbaust, musst du deine Beiträge unter der gleichen oder einer kompatiblen Lizenz wie das Original verbreiten.
Dateiversionen
Klicke auf einen Zeitpunkt, um diese Version zu laden.
| Version vom | Vorschaubild | Maße | Benutzer | Kommentar | |
|---|---|---|---|---|---|
| aktuell | 18:54, 24. Aug. 2015 | | 400 × 240 (2 KB) | Stkl | User created page with UploadWizard |
Dateiverwendung
Die folgende Seite verwendet diese Datei:
