The shortest path problem and variations of it

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

Abstract

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.