Look at the simplified case of N vertices 2 threads.
Divide N / 2 and have each thread solve the solution for each half. There may be an advantage to make the cut isolate nearby vertices (e.g. down the middle). Once each half has been solved, then each vertex need only to make a single probe to each of the other vertices (once) in the other zone. Meaning pick one zone, say zone A, divide vertices in two, have each thread process half the vertices of zone A with distance to all vertices in zone B. All the other paths (chains) have already been determined (weights may need to be adjusted). Extend the method to an arbitrary number of threads.
Effectively what you are doing is constructing chains or hyper threads within each zone by one thread per zone. Once those chains are constructed in each zone, the remaining task is to combine chains between zonesnot vertices. The work should be reduced. Taking care not to compare same chain pair or sequence more than once. As you combine chains, you may need only to check with chains whos ends are at/near the perimeter of the area with the chains at the perimeter of adjacent areas. e.g. look at chains of roads between Illinois and Missouri not Illinois and Massachusetts.
(pick your own adjacent states and disjointed states).