Camino más corto
Lección 12 de 14 del curso Grafos - Serie de Estructuras de Datos #9 de Coddy.
¿Cuál es el número mínimo de aristas necesario para ir de start a end? En un grafo no ponderado (cada arista tiene el mismo costo), la respuesta es exactamente lo que BFS calcula. Debido a que BFS visita los vértices en orden creciente de distancia desde el inicio, la primera vez que alcanzamos end es a través de un camino más corto.
El truco consiste en encolar cada vértice junto con su distancia recorrida hasta el momento. Comienza con (start, 0). Cada vez que descubras un nuevo vecino v desde un vértice a una distancia d, encola (v, d + 1). Cuando v == end, devuelve d + 1.
Dos casos límite. Si start == end, la respuesta es 0. Si BFS termina sin llegar nunca a end, los dos están en diferentes componentes conexas y la respuesta es -1.
Desafío
FácilEscribe una función shortestPath que reciba un array bidimensional de enteros adjacency, un entero start y un entero end, y devuelva la distancia más corta (conteo de aristas) desde start hasta end.
- Si
start == end, devuelve0. - Si
endes inalcanzable desdestart, devuelve-1. - De lo contrario, devuelve el número mínimo de aristas entre ellos.
Debes usar la clase Graph (proporcionada en graph) - no uses elementos integrados del lenguaje (mapas, conjuntos) para modelar la adyacencia. Los datos auxiliares para el algoritmo (conjuntos de visitados, colas) pueden usar tipos de la biblioteca estándar (stdlib).
Pruébalo tú mismo
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start, end;
if (scanf("%d %d %d %d", &n, &m, &start, &end) != 4) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%d\n", shortestPath(adjacency, m, start, end));
return 0;
}