Кратчайший путь с несколькими источниками

Question

Допустим, у нас есть лабиринт, который имеет ширину W и высоту H. В этом лабиринте есть несколько человек и несколько башен.Люди - это источники (S), а башни (D) - места назначения.Следует знать, что у нас есть всезнающий взгляд на лабиринт.У меня такой вопрос:

Если я хочу найти кратчайший путь между различными комбинациями SD, как мне это сделать?

Сначала я могу подумать о наивномРешение, которое включает в себя разбивку на различные операции OSOD SD, проблема в том, что это довольно трудоемко.

Второй вариант - разбить его на S различных операций OSMD.Но я подозреваю, что это все еще слишком мало времени для того, что я ищу.

Мне нужен алгоритм, который может выполнять поиск пути в O (W H) времени.Я не смог найти ничего, что дало бы мне кратчайший путь за O (W H) времени и основанное на MSMD.Надеюсь, кто-то может указать мне правильное направление.

Answer 1

Представьте себе граф, который включает в себя лабиринт, а также начальную и конечную вершины вне лабиринта, с ребром от начальной вершины до каждой S и ребром от каждой D до конечной вершины.

Теперьпоиск в ширину (поскольку весов нет), чтобы найти кратчайший путь от одного начала до одного конца.

Я говорю «представьте» этот граф, потому что на самом деле вам не нужно его строить.В конечном итоге это простой поиск в ширину с небольшими изменениями - вы начинаете со всех S-узлов на корневом уровне и останавливаетесь, когда достигаете любого D.