Advanced search
Start date

The shortest path problem and variations of it

Grant number: 19/09476-4
Support type:Scholarships in Brazil - Scientific Initiation
Effective date (Start): June 01, 2019
Effective date (End): May 31, 2020
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Computational Mathematics
Principal Investigator:Carlos Eduardo Ferreira
Grantee:Thiago Lima Oliveira
Home Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil


In the area of combinatory and graph theory, a known problem is the shortest path problem, this means, given a graph G and two vertices of it find the shortest path between them. In mathematical notation, the problem can be described as given a graph G = (V, E) and two vertices s, t of V and a function cost from the edges to the integers, we want to find the set S of edges that goes from s to t and the sum of the cost of the edges is minimum. This problem arises naturally in diverse areas, the best way to distribute data in a web of computers or in the calculation of the route between two cities, this is why this problem is important in the area. In this project not only the shortest path problem will be studied, but also variants of it, like when we include in the path S found a limitation in the number of edges or others. For example, in the path S found, we can add a function R, from the edges to the integers, and put the restriction that the sum of R (e) for all e in S is less than a given number M. Will also be analyzed the case that it is interesting more than the shortest path but the K shortest paths between two vertices. This project will be developed in 12 months and the objective is to learn about the shortest path problem, and we intend to develop the computational and theoretical knowledge of the student in graph theory. Will also be realized weekly meetings with the supervisor to evaluate the progress of the project.