Graph-basiertes Routing für ein DACH-Carsharing-Anbieter
Übersicht
Worum es bei diesem Projekt geht.
Lade einen OpenStreetMap-Ausschnitt für München (rund 280.000 Knoten) und parse ihn in einen Adjazenzlisten-Graphen. Implementiere zwei Pfadsuch-Algorithmen: Dijkstra mit Min-Heap (Binary Heap selbst implementieren), A* mit Luftlinien-Heuristik. Vergleiche besuchte Knotenanzahl und Wandzeit auf 500 realistischen Anfragen. Optimiere mit Bidirectional Dijkstra. Liefere Quellcode (Java oder Kotlin), Benchmark-Bericht und ein Service-Modul, das in das App-Backend integrierbar ist.
Das Briefing
Was Du tust und was Du zeigst.
Wie implementiert man einen Dijkstra-/A*-basierten Routing-Service auf realen OSM-Daten mit Sub-200-ms-Latenz?
Earning criteria — what you'll demonstrate
- Graphen als Adjazenzliste vs. Adjazenzmatrix für reale Daten korrekt wählen
- Min-Heap als Datenstruktur selbst implementieren statt Standardlib nutzen
- A* mit konsistenter Heuristik korrekt entwerfen
- Bidirektionale Suche als Optimierung verstehen und messen
Studienpassung
Wo dies in Dein Studium passt.
Schärft dieselben Fähigkeiten, die Dein Studium von Dir erwartet.
Fähigkeiten
Fähigkeiten, die Du unter Beweis stellst.
Jede taucht auf Deinem verifizierten Zertifikat auf.
Karrieren
Berufe, auf die dies Dich vorbereitet.
Echte Berufsbezeichnungen. Echte Skill-Brücken. Wähle die, die Deinem Werdegang am nächsten kommt.
Karrierewege, die das aufbaut
Kanonische RollenSoftware-Entwickler:in
Routing-Algorithmen auf echten Graph-Daten zu implementieren ist eines der stärksten CS-Bachelor-Projekte für Bewerbungen in Mobilitäts- und Logistik-Startups im DACH-Raum.
Dieses Projekt schärft
- graphs
- dijkstra
- data-structures
Backend-Entwickler:in
Backend-Entwickler:innen, die Routing- oder Empfehlungs-Services bauen, brauchen genau diese Algorithmus-Tiefe — Standardlib reicht nicht, sobald Latenz-Budgets eng werden.
Dieses Projekt schärft
- a-star
- algorithm-optimization
- graphs
Data Scientist
Graph-Algorithmen sind Grundlage moderner GNN-Forschung (Graph Neural Networks) — wer Dijkstra selbst gebaut hat, versteht spätere ML-Graphenanwendungen tiefer.
Dieses Projekt schärft
- graphs
- heaps
- data-structures
Noch eine Sache