Technische Umsetzung

Technische Dokumentation

Diese Dokumentation enthält die Umsetzung des Projekts und die darin verwendeten Technologien.

Anforderungen

• CMake (Buildtool) in Version 3.30 oder höher
• C23 oder neuer

Entwicklungstools

Für die Entwicklung wurde CLion verwendet, weshalb die bereits vorkonfigurierten build configurations auch für diese Plattform ausgelegt sind. Der Code kann jedoch auch in jeder anderen Entwicklungsumgebung aufgerufen werden, und kompiliert werden kann das Programm ganz ohne Entwicklungsumgebung. Hierfür wird lediglich CMake benötigt.

Codebase

Structs

Für dieses Projekt wird eine Map bzw. ein dictionary im struct DICTIONARY implementiert. Dieses nutzt wiederum weitere structs wie CITY, um eine Stadt abzubilden, und VALUE, welche ein Array von CONNECTIONs enthält, welche eine Verbindung zwischen zwei Städten im Datentyp CITY darstellt.
Weitere Informationen zum Thema Parsing, Einlesen von Dateien und der Verarbeitung des Inputs zu einem Dictionary kann auch unter Karten Parsing nachgelesen werden.

Zusätzliche Informationen

Wird mit der Flag --real die Anwendung im Realfall aktiviert, so fragt das Programm erst nach dem Kraftstoffverbrauch des Fahrzeuges, mit welchem der Nutzer die Strecke absolvieren möchte, und fragt nach dem Preis pro Liter für den Kraftstoff. Mit diesen Werten wird dann am Ende der benötigte Kraftstoffverbrauch, ebenso wie der Preis für diesen Kraftstoff berechnet.
Wird die Flag nicht mit übergeben, wird mit Durchschnittswerten gerechnet. In diesem Fall sind das 7,7l auf 100km und einen Literpreis von 1,85€.

Algorithmus

Nach der optionalen Eingabe des Kraftstoffverbrauchs und des Preises pro Liter berechnet der Algorithmus die Strecke vom Start bis zum Ziel. Hierfür wird der Dijkstra Algorithmus verwendet, welcher den schnellsten Weg von einem Punkt zum anderen finden kann, vor allem über mehrere Knoten dazwischen.
Dieser Algorithmus berechnet, ausgehend vom Startpunkt die Routen zu allen, von diesem Punkt erreichbaren, anderen Punkten. All diese Routen werden in einer Priority Queue gespeichert und anschließend wird auf der kürzesten Gesamtroute weitergerechnet. Dann wird also von dem Punkt, welcher die kleinste Distanz vom Start hat, wieder die Distanz zu allen Nachbarn berechnet und auch diese Routen werden in der Priority Queue gespeichert. Anschließend wird wieder die kürzeste Gesamtroute zur Berechnung herangezogen und der ganze Prozess wiederholt.
Technische ist dies durch eine while schleife umgesetzt, welche abbricht, sobald die Distanz von allen Punkten zu allen anderen Punkten berechnet wurde. Der Speicher für die benötigten Routen wird zu Beginn des Algorithmus allokiert und der benötigte Speicher für jede Route und deren Wegpunkte wird zum benötigten Zeitpunkt allokiert, oder falls bereits allokiert, in der Größe verändert.

Eingabe und Fehlererkennung

Welche Parameter an das Programm übergeben werden können, wird in der Nutzerdokumentation beschrieben. Das Programm fängt falsche oder unzureichende Eingaben ab und gibt Fehlermeldungen über stderr aus. Solche Fehler können zum Beispiel das Fehlen einer Kartendatei, des Starts oder Ziels sein, oder ein Start oder Ziel, welches nicht in der Karte enthalten ist.