3
$\begingroup$

I have a grid graph

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

Mathematica graphics

We can find a shortest from 1 to 144

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

Mathematica graphics

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.

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

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]

Mathematica graphics

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.