Caminho Mais Curto
Lição 12 de 14 do curso Grafos - Série de Estruturas de Dados #9 da Coddy.
Quantas arestas são necessárias, no mínimo, para ir de start até end? Em um grafo não ponderado (cada aresta tem custo igual), a resposta é exatamente o que a BFS calcula. Como a BFS visita os vértices em ordem crescente de distância a partir do início, a primeira vez que alcançamos end é através de um caminho mais curto.
O truque é enfileirar cada vértice junto com sua distância percorrida até o momento. Comece com (start, 0). Cada vez que você descobrir um novo vizinho v a partir de um vértice na distância d, enfileire (v, d + 1). Quando v == end, retorne d + 1.
Dois casos extremos. Se start == end, a resposta é 0. Se a BFS terminar sem nunca alcançar end, os dois estão em componentes conectados diferentes, e a resposta é -1.
Desafio
FácilEscreva uma função shortestPath que recebe um array de inteiros 2D adjacency, um inteiro start e um inteiro end, e retorna a menor distância (contagem de arestas) de start até end.
- Se
start == end, retorne0. - Se
endfor inalcançável a partir destart, retorne-1. - Caso contrário, retorne o número mínimo de arestas entre eles.
Você deve usar a classe Graph (fornecida em graph) - não use recursos nativos da linguagem (mapas, conjuntos) para modelar a adjacência. Dados auxiliares para o algoritmo (conjuntos de visitados, filas) podem usar tipos da biblioteca padrão (stdlib).
Experimente você mesmo
#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;
}