Кратчайший путь
Урок 12 из 14 курса Графы — Серия «Структуры данных» №9 на Coddy.
Какое минимальное количество ребер требуется, чтобы добраться от start до end? В невзвешенном графе (где каждое ребро имеет одинаковую стоимость) ответом является именно то, что вычисляет BFS. Поскольку BFS посещает вершины в порядке увеличения расстояния от начала, первый раз, когда мы достигаем end, происходит по кратчайшему пути.
Хитрость заключается в том, чтобы ставить в очередь каждую вершину вместе с пройденным до нее расстоянием. Начните с (start, 0). Каждый раз, когда вы обнаруживаете нового соседа v из вершины на расстоянии d, ставьте в очередь (v, d + 1). Когда v == end, верните d + 1.
Два граничных случая. Если start == end, ответ — 0. Если BFS завершается, так и не достигнув end, значит, эти две вершины находятся в разных компонентах связности, и ответ — -1.
Задание
ЛегкоНапишите функцию shortestPath, которая принимает двумерный массив целых чисел adjacency, целое число start и целое число end, и возвращает кратчайшее расстояние (количество ребер) от start до end.
- Если
start == end, верните0. - Если
endнедостижим изstart, верните-1. - В противном случае верните минимальное количество ребер между ними.
Вы должны использовать класс Graph (предоставленный в graph) — не используйте встроенные средства языка (словари, множества) для моделирования смежности. Вспомогательные данные для алгоритма (множества посещенных узлов, очереди) могут использовать типы стандартной библиотеки.
Попробуйте сами
#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;
}