Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
    
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
up vote 5 down vote accepted

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]
share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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