Teixeira, M. Thomas (2024) Research Projet : Bi-objective optimization in a directed graph PRE - Research Project, ENSTA.
![]()
| PDF 884Kb |
Abstract
Report of the PRe conducted by Thomas TEIXEIRA during his research internship at Politecnico di Milano from May to August 2024. The internship aimed to generalize Dijkstra's algorithm in a weighted and directed graph within a bi-objective context. Graph theory allows us to mathematically represent numerous real-world situations, as well as the associated problems. One of the most common optimization problems in a graph is undoubtedly finding the shortest path from a source point to the other nodes in the graph, which can be solved, for example, using Dijkstra’s algorithm. In this report, we focus on an extension of Dijkstra’s algorithm that solves a bi-objective optimization problem. Here, we consider not a graph where each arc has a weight x ∈ R, but rather a graph where the arcs have a pair of weights (x, y) ∈ R2. Our goal is to design an algorithm that solves this problem with the lowest possible complexity.
Item Type: | Thesis (PRE - Research Project) |
---|---|
Uncontrolled Keywords: | graph, optimization, Dijkstra, algorithm, C++, bi-objective |
Subjects: | Mathematics and Applications |
ID Code: | 10213 |
Deposited By: | Thomas TEIXEIRA |
Deposited On: | 03 sept. 2024 17:02 |
Dernière modification: | 03 sept. 2024 17:02 |
Repository Staff Only: item control page