Interaktives Python-Labor

Dijkstra's Shortest Path

Der Playground wird beim Laden automatisch ausgeführt. Klicken Sie auf Meinen Code ausführen, um Ihren eigenen Python-Code zu verfolgen — jeder Schritt live animiert.

Erklären·Zeile für Zeile

Wiedergeben·Schritt für Schritt

Herausforderung·Geführte Hinweise

XP·...

Datenfluss-Pipeline

mastery Lernpfad

Dijkstra's Shortest Path

0/1 Knapsack DP

Longest Common Subsequence

Coin Change DP

Topological Sort (Kahn's)

Kruskal's MST

Trie (Prefix Tree)

Floyd-Warshall All-Pairs Shortest Path

Segment Tree for Range Queries

Bit Manipulation Tricks

Erklären

Line 3

dijkstra(graph, start=0) called. Initialize distance table.

Warum dieser Ansatz?

We call dijkstra with start=0. The function will compute shortest distances from node 0 to all other nodes using a greedy approach with a min-heap.

Structured Explanation

Overview

Dijkstras Algorithmus findet kürzeste Pfade von einem Quellknoten zu allen anderen bei nicht-negativen Kantengewichten.

Analogy

Eine Blase finalisierter Kürzestwegdistanzen breitet sich von der Startstadt nach außen aus.

Step-by-step

Setze dist[quelle]=0, alle anderen=∞; füge Quelle in Min-Heap.
Solange Heap nicht leer: extrahiere Knoten u mit kleinstem dist.
Für jede Kante (u,v,w): wenn dist[u]+w < dist[v]: aktualisiere und füge v in Heap.
Extrahierte Knoten haben finale Distanzen.

Visual

Besuchte Menge wächst; Frontier-Kanten entspannen Distanzen in einem Kürzester-Pfad-Baum.

Common mistakes

Dijkstra bei negativen Kanten verwenden (falsch – Bellman-Ford nutzen).
Veraltete Heap-Einträge nicht überspringen nach besseren Distanz-Aktualisierungen.
Array-Priority-Queue verwenden → O(V²) auf großen Graphen.

Practice questions

Auf einem 5-Knoten-gewichteten Graphen ausführen und dist pro Schritt tabellieren.
Pfade mit Parent-Zeigern rekonstruieren.
Binären Heap vs. Fibonacci-Heap Komplexität vergleichen.

Time

O((V+E) log V) mit Binär-Heap

Space

O(V) für dist/parent/visited

Komplexität

Zeit

O((V + E) log V)

Speicher

O(V)

Komplexitätsübersicht

O(1)

O(log n)

O(n)

O(n log n)

O(n²)

n = 8bereich 1-20

BEI N = 8

Komplexität	Operationen
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

Herausforderung

Dijkstra-Algorithmus

Hinweis

Kürzeste Pfade in Graphen mit nicht-negativen Gewichten.

Code-Studio

Dijkstra's Shortest Path

Monaco Bereit

Python Bereit

lesson.pyline 3

Loading editor...

Ausgabekonsole

1 lines

❯ {0: 0, 1: 3, 2: 1, 3: 4}

Praxisanwendungen

1

GPS-Navigation und kürzeste Routenfindung

2

Netzwerk-Routingprotokolle (OSPF)

3

Pathfinding in Spiel-KI

Comments

Loading comments...