Если все симметрично, то наиболее разумный вариант — поиск в ширину (это то, что называют волной) с 2х сторон, по 2 шага с каждой. Итого будет два списка по 100^2 вершин, в котором нужно найти пересечения, и их отсортировать. С учетом того, что полученных путей почти всегда будет менее 10000, то наверное нет смысла париться, можно смело запихнуть все в кучу и пройтись быстрой сортировкой (хотя зависит от системы, если это место будет занимать значительную часть ресурсов — то наверняка можно придумать что получше).
И — такой вариант примерно в 100^2 / 2 раз быстрее поиска из одной вершины. Чуть-чуть не подумав, вычислительно простую задачу можно легко превратить в ресурсоемкого монстра :)
