Решил, пока сам попроверять.
И нашел проблему, не получается сделать идеальный алгоритм.
Проблема в смежных зонах без городов.
У них нет координаты куда нужно вести дорогу, поэтому приходится рекурсивно искать зону с городом и соединять ее со другой зоной с городом.
В большинстве случаев, все ок.
Но иногда из-за багнутого прохода или просто из-за близости зон, зоны с городами могу соединиться напрямую минуя смежку.
Как это победить я не представляю.