# Búsqueda de caminos mínimos en grafos ponderados

_© F.J. Madrid Cuevas (fjmadrid@uco.es)
Estructuras de Datos. Grado de Ingeniería Informática. Universidad de Córdoba. España_

## Objetivo

- Aprender a implementar el TAD Grafo usando una matriz asociativa.
- Aprender a implementar una cola de prioridad.
- Implementar el algoritmo de Dijkstra.
- Implementar el algoritmo de Floyd.
- Implementar el algoritmo A\*.
- Aprender a utilizar el tipo c++ std::tuple [1].

## Descripción

Existen varios algoritmos para buscar caminos mínimos en grafos ponderados. Podemos destacar:

- **Algoritmo de Dijkstra**: buscar todos los caminos mínimos desde un vértice origen al resto de vértices.
- **Algoritmo de Floyd**: buscar todos los caminos mínimos entre dos pares de vértices.
- **Algoritmo A\***: busca el camino más corto entre dos vértices usando una heurística para guiar la búsqueda.

## Evaluación

Mira el fichero `TESTS.json` para ver los tests y su peso en la evaluación.

Se recomienda la siguiente forma de realizar la práctica:

- **Primera semana**: tests de WGraph y PQueue.
- **Segunda semana**: tests de Dijkstrap, A* y Floyd.

Puedes usar el tipo std::priority_queue [2] en vez de implementar el TAD "PriorityQueue" en los algoritmos Dijkstra y A\*.

## Calendario de entregas

Ver fichero `DATES.json`.

## Referencias

[1] [https://en.cppreference.com/w/cpp/utility/tuple].
[2] [https://en.cppreference.com/w/cpp/container/priority_queue].