Как соединить две точки, не пересекая другой путь?

Предположим, что у меня есть следующая сетка. Мне нужно соединить пары букв. Не только одинаковые буквы должны быть соединены, но я также должен убедиться, что соединительные пути не пересекаются друг с другом. Какой алгоритм мог бы мне подсказать, можно ли соединить все пары без пересечения путей и кратчайшего пути?

Я понимаю, что это проблема графа, и часть кратчайшего пути может быть решена с помощью BFS. В чем я не уверен, так это в пересечении путей.

  +---+---+---+---+---+---+---+---+
  | A |   |   | B |   |   |   |   |
  +-------------------------------+
  |   |   |   |   |   |   |   |   |
  +-------------------------------+
  |   |   | B |   |   |   | D |   |
  +-------------------------------+
  |   |   |   |   |   |   |   |   |
  +-------------------------------+
  |   | C |   |   | C |   |   |   |
  +-------------------------------+
  |   |   |   | A |   |   |   |   |
  +-------------------------------+
  |   |   |   |   |   |   | D |   |
  +-------------------------------+
  |   |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+