# How to find the shortest path going through some specified vertices

I have a grid graph

g = GridGraph[{12, 12}, VertexLabels -> "Name"]


We can find a shortest from 1 to 144

path = FindShortestPath[g, 1, 144];
HighlightGraph[g, PathGraph[path]]


But my question is how to find the shortest path from 1 to 144 and in the meantime this path go through vertex 50, 64, 103.

The post have not the demand of the order.And I havenot mention it before too.So update this case.

-
As stated that seems like it will be quite a few paths. – Daniel Lichtblau Mar 27 at 15:40
@DanielLichtblau Thanks for point out.I have update the question just now. – yode Mar 27 at 15:51

If the vertices v = {1, 50, 64, 103, 144} are to be visited in the specified order, you can use

subpaths = Partition[v, 2, 1]


{{1, 50}, {50, 64}, {64, 103}, {103, 144}}

fullpath = DeleteDuplicates[Join @@ FindShortestPath@g @@@ subpaths]


{1, 2, 14, 26, 38, 50, 51, 52, 64, 65, 66, 67, 79, 91, 103, 104, 105, 106, 107, 108, 120, 132, 144}

HighlightGraph[g, PathGraph[fullpath], ImagePadding -> 20]


Alternatively, you can get the same result defining a function:

pathF[g_Graph] := DeleteDuplicates[DeveloperPartitionMap[
##&@@ FindShortestPath@g@@# &, #, 2, 1]] &;
HighlightGraph[g, PathGraph[pathF[g][v]], ImagePadding -> 20]
`
-
Does this allow for the possibility that the shortest path may not go in precisely the order $1\rightarrow50\rightarrow64\rightarrow103\rightarrow144$? – QuantumDot Mar 27 at 13:41
@QuantumDot, very good point; it doesn't. – kglr Mar 27 at 13:46
Oh,sorry the order isn't required.I will updat this.In any case,you are very good at this.:) – yode Mar 27 at 13:55