A reproducible comparison of Dijkstra, A*, SPFA, Floyd-Warshall, and BFS on one shared weighted graph. The project separates two questions that are often mixed together:
- Which route has the lowest total travel cost?
- Which route uses the fewest road segments?
Dijkstra, A*, SPFA, and Floyd-Warshall all return a minimum weighted cost of 5.10 on the same network. BFS returns a two-edge route with cost 8.80 because BFS minimizes hops, not weighted distance.
| Algorithm | Objective | Weighted cost | Hops |
|---|---|---|---|
| Dijkstra | Minimum weight | 5.10 | 4 |
| A* | Minimum weight | 5.10 | 4 |
| SPFA | Minimum weight | 5.10 | 4 |
| Floyd-Warshall | Minimum weight | 5.10 | 4 |
| BFS | Minimum hops | 8.80 | 2 |
This is the methodological correction at the center of the project: algorithms are compared on the same graph, and BFS is reported against its actual objective instead of being declared a distance winner.
- One common synthetic network for fair comparison
- Original algorithm implementations instead of black-box calls
- Euclidean A* heuristic validated against edge costs
- Automated tests enforcing agreement among weighted shortest-path methods
- Reproducible CSV and PNG outputs
- No home address, real route, API key, or private location data
src/route_optimization/
algorithms.py # Dijkstra, A*, SPFA, Floyd-Warshall, BFS
network.py # deterministic fictional road network
analysis.py # benchmark, CSV export, and visualizations
tests/
test_algorithms.py
outputs/
algorithm_comparison.csv
route_comparison.png
weighted_costs.png
python -m pip install -e ".[dev]"
python -m route_optimization.analysis
pytestRuntime measurements in the CSV are descriptive microbenchmarks for this small graph, not universal rankings. Algorithmic complexity and graph structure matter more than a single local timing.
The graph is fictional and generated directly in network.py. Node labels and coordinates are synthetic. Earlier exploratory notebooks were used only as inspiration for the learning objective and are intentionally excluded because they mixed graph definitions and comparison criteria.
Aaron Fernandez Pinto, Data Science student at Universidad Autónoma de Baja California (UABC).
Español
Una comparación reproducible de Dijkstra, A*, SPFA, Floyd-Warshall y BFS sobre un mismo grafo ponderado. El proyecto separa dos preguntas que suelen mezclarse:
- ¿Qué ruta tiene el menor costo total de viaje?
- ¿Qué ruta usa la menor cantidad de segmentos viales?
Dijkstra, A*, SPFA y Floyd-Warshall devuelven un costo ponderado mínimo de 5.10 en la misma red. BFS devuelve una ruta de dos aristas con costo 8.80 porque BFS minimiza saltos, no distancia ponderada.
| Algoritmo | Objetivo | Costo ponderado | Saltos |
|---|---|---|---|
| Dijkstra | Peso mínimo | 5.10 | 4 |
| A* | Peso mínimo | 5.10 | 4 |
| SPFA | Peso mínimo | 5.10 | 4 |
| Floyd-Warshall | Peso mínimo | 5.10 | 4 |
| BFS | Saltos mínimos | 8.80 | 2 |
Esta es la corrección metodológica central del proyecto: los algoritmos se comparan sobre el mismo grafo y BFS se reporta según su objetivo real en lugar de declararlo ganador en distancia.
- Una red sintética común para una comparación justa
- Implementaciones originales de los algoritmos en lugar de llamadas de caja negra
- Heurística euclidiana de A* validada contra los costos de las aristas
- Pruebas automatizadas que exigen concordancia entre los métodos de ruta mínima ponderada
- Salidas CSV y PNG reproducibles
- Sin domicilio, ruta real, clave de API ni datos privados de ubicación
src/route_optimization/
algorithms.py # Dijkstra, A*, SPFA, Floyd-Warshall, BFS
network.py # red vial ficticia y determinista
analysis.py # benchmark, exportación CSV y visualizaciones
tests/
test_algorithms.py
outputs/
algorithm_comparison.csv
route_comparison.png
weighted_costs.png
python -m pip install -e ".[dev]"
python -m route_optimization.analysis
pytestLas mediciones de tiempo de ejecución en el CSV son microbenchmarks descriptivos para este grafo pequeño, no rankings universales. La complejidad algorítmica y la estructura del grafo importan más que una sola medición local.
El grafo es ficticio y se genera directamente en network.py. Las etiquetas y coordenadas de los nodos son sintéticas. Los notebooks exploratorios anteriores se usaron sólo como inspiración para el objetivo de aprendizaje y se excluyeron intencionalmente porque mezclaban definiciones de grafos y criterios de comparación.
Aaron Fernandez Pinto, estudiante de Ciencia de Datos en la Universidad Autónoma de Baja California (UABC).