Analysis and Implementation of Algorithms for Bicriteria Shortest Paths Problems

Questa tesi si pone l'obbiettivo di affrontare ed analizzare un problema di pathfinding partendo da un'analisi di alcuni algoritmi per la ricerca del percorso più breve su normali grafi, per poi ampliare lo studio e concentrarsi su algoritmi che calcolano molteplici percorsi su grafi che utilizzano due pesi per ogni arco. Gli algoritmi per i grafi `bicriteria' (appunto che considerano due pesi su ogni arco) verranno analizzati, implementati e le loro soluzioni confrontate con gli altri algoritmi, al fine di individuare i più efficienti in termini di tempo di elaborazione e quelli che riescono a minimizzare al meglio i pesi degli archi dei cammini trovati, quindi valutando quantità e qualità delle soluzioni. Dato che, lo studio di algoritmi per la ricerca del percorso più breve in grafi classici è piuttosto celebre in letteratura, è ormai facile trovare implementazioni che permettano di risolvere questo problema. Verrà effettuata quindi una rapida implementazione ed analisi riguardante gli algoritmi `monocriteria'. Per agli algoritmi che lavorano in grafi con più pesi, per i quali è più difficile reperire implementazioni ed analisi, ci sarà una spiegazione più approfondita ed accurata, soffermandosi anche su casi particolari e indicando le scelte implementative fatte per ottimizzare al meglio le loro prestazioni. L'analisi dei risultati confronterà, come già detto, l'insieme delle soluzioni calcolate dai vari algoritmi ed i loro tempi di elaborazione. Inoltre i suddetti algoritmi verranno utilizzati su mappe di alcune città, prese come esempio, per poter fare un confronto visivo sui cammini minimi trovati ed i nodi visitati durante l'elaborazione degli algoritmi; in modo da semplificare e rendere più immediato il confronto tra le varie implementazioni.