Cool problem.

In advance I'll warn that you might have a hard time understanding my answer if you haven't worked with programming and algorithms before. I'll try my best to explain and be available to answer questions.

There is more than one way to approach the problem.

It's possible that due to lots of symmetry, this problem has a closed-form expression solution method, but with just 14 vertices it may be easier to look in other directions first.

One approach is to think of the problem as a Travelling salesman problem, where edges between non-connected vertices are given "infinite distance" (in practice, just assign a very high number). Although TSP is in general a hard problem, 14 vertices is certainly doable, but you would need to write a computer program or use existing software tools to get your answer. Solutions to TSP are, in the general case, given in terms of analgorithmrather than in terms of a closed-form expression.

There are TSP solvers that can be downloaded, like the Concorde TSP Solver, or you could try reading up on how to code your own algorithm.

I'll go for a different approach, which can be written without knowledge of TSP algorithms: I'll use a backtracking algorithm, which is similar to using brute force, but more optimized. (Brute force means trying every possible path.)

Consider that 8 of the vertices have 6 edges each, and the other 6 vertices have 4 edges each. We can encode a path by labeling the vertices, and then for each vertex store the value of the next vertex. We won't actually be using this encoding, it's just to get an estimate of how much time/memory the algorithm will take. For simplicity, allow the last vertex to point to another vertex. Then 6^8 * 4^6 = 6,879,707,136 is the number of possible codes in our encoding scheme, but not all codes correspond to valid paths, thus our estimate is high. Given modern computing power and the estimate, backtracking should be doable in a reasonable amount of run time.

So, we choose a labeling scheme, and while the choice is arbitrary, we can try to choose one that makes things easier to keep track of. The most straightforward way I can think of is to place the cube with one corner on the origin and the opposite corner on the point (1,1,1). With binary, we have

(0,0,0) -> 0

(0,0,1) -> 1

(0,1,0) -> 2

...

(1,1,1) -> 7

So we've labeled the corners of the cube, now we need to label the centers of each face. We can define a center from the four corners on the same face, and I assigned them lexicographically:

(0,1,2,3) -> 8

(0,1,4,5) -> 9

(0,2,4,6) -> 10

(1,3,5,7) -> 11

(2,3,6,7) -> 12

(4,5,6,7) -> 13

Now for distance, there are only two possibilities: 1, or .

One last thing needs to be addressed: it is possible that the start and end nodes are both corners, both centers, or one corner and one center. Without loss of generality, we can start with a corner and find the shortest distance, then start over with a center and find the shortest distance, and take whichever of the two is shortest.

Basically, everything is set up, and we just need to write the program. Where backtracking comes in: we store the shortest path distance achieved so far, and if any path exceeds that distance, we stop following the current path and go back to a previous state (we backtrack).

Note that the problem doesn't ask us what the shortest path is, just the length of the path. For fun, we'll keep track of the path itself too.

Here is some Java code:

Output:Code:// http://www.mathhelpforum.com/math-help/pre-algebra-algebra/140117-cubes-networks-shortest-path.html import java.util.ArrayList; public class CubeGraph { private static int[][] map; private static double min = 1000, min1, sq22 = Math.sqrt(2)/2.0; private static ArrayList<Integer> minPath; public static void init() { // map each vertex to either four or six other vertices // using hard-coded values; could also generate with method int[] v0 = {1, 2, 4, 8, 9, 10}; int[] v1 = {0, 3, 5, 8, 9, 11}; int[] v2 = {0, 3, 6, 8, 10, 12}; int[] v3 = {1, 2, 7, 8, 11, 12}; int[] v4 = {0, 5, 6, 9, 10, 13}; int[] v5 = {1, 4, 7, 9, 11, 13}; int[] v6 = {2, 4, 7, 10, 12, 13}; int[] v7 = {3, 5, 6, 11, 12, 13}; int[] v8 = {0, 1, 2, 3}; int[] v9 = {0, 1, 4, 5}; int[] v10 = {0, 2, 4, 6}; int[] v11 = {1, 3, 5, 7}; int[] v12 = {2, 3, 6, 7}; int[] v13 = {4, 5, 6, 7}; int[][] map1 = {v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13}; map = deepCopy(map1); } public static void main(String[] args) { long time = System.currentTimeMillis(); init(); ArrayList<Integer> path = new ArrayList<Integer>(); boolean[] visited = new boolean[14]; backtrack(path, visited, 0, 0); min1 = min; System.out.println("Starting on corner: min dist = " + min + " and path = " + minPath); min = 1000; path = new ArrayList<Integer>(); visited = new boolean[14]; backtrack(path, visited, 8, 0); System.out.println("Starting on center: min dist = " + min + " and path = " + minPath); System.out.println("in " + ((System.currentTimeMillis() - time) / 1000.0) + " s"); } public static void backtrack(ArrayList<Integer> path, boolean[] visited, int vertex, double dist) { if (dist > min) return; visited[vertex] = true; path.add(vertex); if (path.size() == 14) { if (dist < min) { min = dist; minPath = new ArrayList<Integer>(); minPath.addAll(path); } return; } for (int i = 0; i < map[vertex].length; i++) { int nextV = map[vertex][i]; if (!visited[nextV]) backtrack(new ArrayList<Integer>(path), visited.clone(), nextV, dist + getDist(vertex, nextV)); } } public static double getDist(int v1, int v2) { return (v1 > 7 || v2 > 7) ? sq22 : 1; } public static int[][] deepCopy(int[][] orig) { int[][] copy = new int[orig.length][]; for (int i = 0; i < orig.length; i++) copy[i] = orig[i].clone(); return copy; } }

Which is faster than I expected. I believe the code is bug-free, but confirmation is always welcome. It can be seen that the minimum path I got has a distance of .Code:Starting on corner: min dist = 9.485281374238573 and path = [0, 1, 8, 2, 10, 4, 9, 5, 11, 3, 12, 6, 13, 7] Starting on center: min dist = 9.778174593052025 and path = [8, 0, 1, 3, 11, 5, 9, 4, 10, 2, 12, 6, 13, 7] in 0.375 s

My guess is that a TSP solver would get the same answer faster, but although I'm curious, I'm not quite curious enough to set it up and compare, haha.

Thanks for the fun problem!