Najkrótsza ścieżka
Lekcja 12 z 14 w kursie Grafy – struktury danych, seria nr 9 w Coddy.
Ile najmniej krawędzi potrzeba, aby przejść z start do end? W grafie nieważonym (każda krawędź ma taki sam koszt) odpowiedź jest dokładnie tym, co oblicza BFS. Ponieważ BFS odwiedza wierzchołki w kolejności rosnącej odległości od początku, za pierwszym razem docieramy do end najkrótszą ścieżką.
Sztuczka polega na umieszczaniu w kolejce każdego wierzchołka wraz z dotychczasową odległością. Zacznij od (start, 0). Za każdym razem, gdy odkryjesz nowego sąsiada v wierzchołka znajdującego się w odległości d, umieść w kolejce (v, d + 1). Gdy v == end, zwróć d + 1.
Dwa przypadki brzegowe. Jeśli start == end, odpowiedzią jest 0. Jeśli BFS zakończy się, zanim dotrze do end, oba wierzchołki znajdują się w różnych składowych spójnych, a odpowiedzią jest -1.
Wyzwanie
ŁatwyNapisz funkcję shortestPath, która przyjmuje dwuwymiarową tablicę liczb całkowitych adjacency, liczbę całkowitą start i liczbę całkowitą end, a następnie zwraca najkrótszą odległość (liczbę krawędzi) od start do end.
- Jeśli
start == end, zwróć0. - Jeśli nie można dotrzeć do
endzstart, zwróć-1. - W przeciwnym razie zwróć minimalną liczbę krawędzi między nimi.
Musisz użyć klasy Graph (udostępnionej w graph) — nie używaj wbudowanych typów języka (map, zbiorów) do modelowania sąsiedztwa. Dane pomocnicze algorytmu (zbiory odwiedzonych wierzchołków, kolejki) mogą korzystać z typów biblioteki standardowej.
Spróbuj swoich sił
#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;
}
Wszystkie lekcje w sekcji Grafy – struktury danych, seria nr 9
Poćwicz samodzielnie: Kompilator C online