floyd函数

    1. % floyd.m
    2. % 采用floyd算法计算图a中每对顶点最短路
    3. % d是矩离矩阵
    4. % r是路由矩阵
    5. function [d,r]=floyd(a)
    6. n=size(a,1);
    7. % 初始化距离矩阵
    8. d=a;
    9. % 初始化路由矩阵
    10. for i=1:n
    11. for j=1:n
    12. if a(i,j) ~= inf
    13. r(i,j)=j;
    14. end
    15. end
    16. end
    17. r;
    18. % Floyd算法开始
    19. for k=1:n
    20. for i=1:n
    21. for j=1:n
    22. if d(i,k)+d(k,j)<d(i,j)
    23. d(i,j)=d(i,k)+d(k,j);
    24. r(i,j)=r(i,k);
    25. end
    26. end
    27. end
    28. k;
    29. d;
    30. r;
    31. end

    DIsplayPath函数

    1. % DisplayPath.m 打印路径函数
    2. function DisplayPath(route, start, dest)
    3. % 打印出任意两点之间的最短路径
    4. % route : 路由表
    5. % start : 起点index
    6. % dest : 终点index
    7. i = 1;
    8. while 1
    9. if(route(start, dest) ~= dest)
    10. fprintf('V%s -> ', num2str(start));
    11. start = route(start, dest);
    12. else
    13. fprintf('V%s -> ', num2str(start));
    14. fprintf('V%s\n', num2str(dest));
    15. break;
    16. end
    17. end

    findNaN函数

    1. function result_matrix = findNaN(matrix)
    2. %找到矩阵中NaN,并用同列前一个数字替换
    3. %计算矩阵行列数(r:行数,c:列数)
    4. [r,c] = size(matrix);
    5. temp = isnan(matrix);
    6. result_matrix = matrix;
    7. for i=1:c
    8. for j=1:r
    9. if temp(j,i) == 1
    10. result_matrix(j,i) = inf;
    11. end
    12. end
    13. end
    14. end

    命令行窗口执行的函数

    1. a = xlsread('副本road1.xlsx')
    2. a = findNaN(a)
    3. [d,r]=floyd(a)
    4. disp('--------------------------')
    5. for i = 1 : 27
    6. for j = 1 : 27
    7. DisplayPath(r, i, j);
    8. end
    9. end

    执行结果
    d
    0 1 2 2 3 3 4 5 5 6 7 8 7 7 6 6 5 6 6 5 4 4 3 2 1 2 3
    1 0 1 2 3 4 5 6 6 7 8 9 8 8 7 7 6 7 7 6 5 5 4 3 2 3 4
    2 1 0 1 2 3 4 5 5 6 7 8 7 7 6 6 5 6 6 5 4 4 3 2 2 3 4
    2 2 1 0 1 2 3 4 4 5 6 7 6 6 5 5 4 5 5 4 3 3 2 1 1 2 3
    3 3 2 1 0 1 2 3 4 5 6 7 6 6 5 5 4 5 5 4 3 3 2 1 2 2 3
    3 4 3 2 1 0 1 2 3 4 5 6 5 5 4 4 3 4 4 3 2 2 1 1 2 2 3
    4 5 4 3 2 1 0 1 2 3 4 5 4 4 3 3 3 4 4 3 2 1 2 2 3 3 3
    5 6 5 4 3 2 1 0 1 2 3 4 3 3 2 2 2 3 4 3 2 1 2 3 4 3 3
    5 6 5 4 4 3 2 1 0 1 2 3 2 2 1 1 1 2 3 3 2 1 2 3 4 3 3
    6 7 6 5 5 4 3 2 1 0 1 2 1 2 1 2 2 3 4 4 3 2 3 4 5 4 4
    7 8 7 6 6 5 4 3 2 1 0 1 1 2 2 3 3 4 5 5 4 3 4 5 6 5 5
    8 9 8 7 7 6 5 4 3 2 1 0 1 1 2 2 3 3 4 4 4 4 5 6 7 6 5
    7 8 7 6 6 5 4 3 2 1 1 1 0 1 1 2 3 3 4 4 4 3 4 5 6 5 5
    7 8 7 6 6 5 4 3 2 2 2 1 1 0 1 1 2 2 3 3 3 3 4 5 6 5 4
    6 7 6 5 5 4 3 2 1 1 2 2 1 1 0 1 2 2 3 3 3 2 3 4 5 4 4
    6 7 6 5 5 4 3 2 1 2 3 2 2 1 1 0 1 1 2 2 2 2 3 4 5 4 3
    5 6 5 4 4 3 3 2 1 2 3 3 3 2 2 1 0 1 2 2 1 2 2 3 4 3 2
    6 7 6 5 5 4 4 3 2 3 4 3 3 2 2 1 1 0 1 1 2 3 3 4 5 4 3
    6 7 6 5 5 4 4 4 3 4 5 4 4 3 3 2 2 1 0 1 2 3 3 4 5 4 3
    5 6 5 4 4 3 3 3 3 4 5 4 4 3 3 2 2 1 1 0 1 2 2 3 4 3 2
    4 5 4 3 3 2 2 2 2 3 4 4 4 3 3 2 1 2 2 1 0 1 1 2 3 2 1
    4 5 4 3 3 2 1 1 1 2 3 4 3 3 2 2 2 3 3 2 1 0 1 2 3 2 2
    3 4 3 2 2 1 2 2 2 3 4 5 4 4 3 3 2 3 3 2 1 1 0 1 2 1 2
    2 3 2 1 1 1 2 3 3 4 5 6 5 5 4 4 3 4 4 3 2 2 1 0 1 1 2
    1 2 1 1 2 2 3 4 4 5 6 7 6 6 5 5 4 5 5 4 3 3 2 1 0 1 2
    2 3 2 2 2 2 3 3 3 4 5 6 5 5 4 4 3 4 4 3 2 2 1 1 1 0 1
    3 4 3 3 3 3 3 3 3 4 5 5 5 4 4 3 2 3 3 2 1 2 2 2 2 1 0
    r
    1 2 2 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25
    1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 1 1 1
    2 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
    25 3 3 4 5 5 5 5 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 25 24 24
    4 4 4 4 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 24 4 24 24
    24 5 5 5 5 6 7 7 7 7 7 7 7 7 7 7 23 23 23 23 23 7 23 24 24 23 23
    6 6 6 6 6 6 7 8 8 8 8 8 8 8 8 8 8 8 22 22 22 22 6 6 6 6 22
    7 7 7 7 7 7 7 8 9 9 9 9 9 9 9 9 9 9 9 22 22 22 22 7 7 22 22
    22 22 22 22 8 8 8 8 9 10 10 10 10 15 15 16 17 16 16 16 17 22 22 22 22 22 17
    9 9 9 9 9 9 9 9 9 10 11 11 13 13 15 9 9 9 9 9 9 9 9 9 9 9 9
    10 10 10 10 10 10 10 10 10 10 11 12 13 12 10 10 10 10 10 10 10 10 10 10 10 10 10
    14 14 14 14 11 11 11 11 11 11 11 12 13 14 13 14 14 14 14 14 14 11 14 14 14 14 14
    10 10 10 10 10 10 10 10 10 10 11 12 13 14 15 14 10 14 14 14 10 10 10 10 10 10 10
    16 16 16 16 15 15 15 15 15 13 12 12 13 14 15 16 16 16 16 16 16 15 16 16 16 16 16
    9 9 9 9 9 9 9 9 9 10 10 13 13 14 15 16 9 16 16 16 9 9 9 9 9 9 9
    17 17 17 17 9 9 9 9 9 9 9 14 14 14 15 16 17 18 18 18 17 9 17 17 17 17 17
    21 21 21 21 21 21 9 9 9 9 9 16 9 16 9 16 17 18 18 18 21 9 21 21 21 21 21
    17 17 17 17 17 17 16 16 16 16 16 16 16 16 16 16 17 18 19 20 17 16 17 17 17 17 17
    20 20 20 20 20 20 20 18 18 18 18 18 18 18 18 18 18 18 19 20 20 20 20 20 20 20 20
    21 21 21 21 21 21 21 21 18 18 18 18 18 18 18 18 18 18 19 20 21 21 21 21 21 21 21
    23 23 23 23 23 23 22 22 17 17 17 17 17 17 17 17 17 17 20 20 21 22 23 23 23 23 27
    23 23 23 23 7 7 7 8 9 9 9 9 9 9 9 9 9 9 21 21 21 22 23 23 23 23 21
    24 24 24 24 6 6 6 22 22 22 22 21 22 21 22 21 21 21 21 21 21 22 23 24 24 26 21
    25 4 4 4 5 6 6 6 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 24 25 26 26
    1 1 3 4 4 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 25 26 26
    25 25 25 24 24 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 24 25 26 27
    26 26 26 26 26 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 26 26 26 27
    路径导出


    V1 -> V1
    V1 -> V2
    V1 -> V2 -> V3
    V1 -> V25 -> V4
    V1 -> V25 -> V4 -> V5
    V1 -> V25 -> V24 -> V6
    V1 -> V25 -> V24 -> V6 -> V7
    V1 -> V25 -> V24 -> V6 -> V7 -> V8
    V1 -> V25 -> V24 -> V23 -> V22 -> V9
    V1 -> V25 -> V24 -> V23 -> V22 -> V9 -> V10
    V1 -> V25 -> V24 -> V23 -> V22 -> V9 -> V10 -> V11
    V1 -> V25 -> V24 -> V23 -> V21 -> V17 -> V16 -> V14 -> V12
    V1 -> V25 -> V24 -> V23 -> V22 -> V9 -> V10 -> V13
    V1 -> V25 -> V24 -> V23 -> V21 -> V17 -> V16 -> V14
    V1 -> V25 -> V24 -> V23 -> V22 -> V9 -> V15
    V1 -> V25 -> V24 -> V23 -> V21 -> V17 -> V16
    V1 -> V25 -> V24 -> V23 -> V21 -> V17
    V1 -> V25 -> V24 -> V23 -> V21 -> V17 -> V18
    V1 -> V25 -> V24 -> V23 -> V21 -> V20 -> V19
    V1 -> V25 -> V24 -> V23 -> V21 -> V20
    V1 -> V25 -> V24 -> V23 -> V21
    V1 -> V25 -> V24 -> V23 -> V22
    V1 -> V25 -> V24 -> V23
    V1 -> V25 -> V24
    V1 -> V25
    V1 -> V25 -> V26
    V1 -> V25 -> V26 -> V27
    V2 -> V1
    V2 -> V2
    V2 -> V3
    V2 -> V3 -> V4
    V2 -> V3 -> V4 -> V5
    V2 -> V3 -> V4 -> V5 -> V6
    V2 -> V3 -> V4 -> V5 -> V6 -> V7
    V2 -> V3 -> V4 -> V5 -> V6 -> V7 -> V8
    V2 -> V3 -> V4 -> V24 -> V23 -> V22 -> V9
    V2 -> V3 -> V4 -> V24 -> V23 -> V22 -> V9 -> V10
    V2 -> V3 -> V4 -> V24 -> V23 -> V22 -> V9 -> V10 -> V11
    V2 -> V3 -> V4 -> V24 -> V23 -> V21 -> V17 -> V16 -> V14 -> V12
    V2 -> V3 -> V4 -> V24 -> V23 -> V22 -> V9 -> V10 -> V13
    V2 -> V3 -> V4 -> V24 -> V23 -> V21 -> V17 -> V16 -> V14
    V2 -> V3 -> V4 -> V24 -> V23 -> V22 -> V9 -> V15
    V2 -> V3 -> V4 -> V24 -> V23 -> V21 -> V17 -> V16
    V2 -> V3 -> V4 -> V24 -> V23 -> V21 -> V17
    V2 -> V3 -> V4 -> V24 -> V23 -> V21 -> V17 -> V18
    V2 -> V3 -> V4 -> V24 -> V23 -> V21 -> V20 -> V19
    V2 -> V3 -> V4 -> V24 -> V23 -> V21 -> V20
    V2 -> V3 -> V4 -> V24 -> V23 -> V21
    V2 -> V3 -> V4 -> V24 -> V23 -> V22
    V2 -> V3 -> V4 -> V24 -> V23
    V2 -> V3 -> V4 -> V24
    V2 -> V1 -> V25
    V2 -> V1 -> V25 -> V26
    V2 -> V1 -> V25 -> V26 -> V27
    V3 -> V2 -> V1
    V3 -> V2
    V3 -> V3
    V3 -> V4
    V3 -> V4 -> V5
    V3 -> V4 -> V5 -> V6
    V3 -> V4 -> V5 -> V6 -> V7
    V3 -> V4 -> V5 -> V6 -> V7 -> V8
    V3 -> V4 -> V24 -> V23 -> V22 -> V9
    V3 -> V4 -> V24 -> V23 -> V22 -> V9 -> V10
    V3 -> V4 -> V24 -> V23 -> V22 -> V9 -> V10 -> V11
    V3 -> V4 -> V24 -> V23 -> V21 -> V17 -> V16 -> V14 -> V12
    V3 -> V4 -> V24 -> V23 -> V22 -> V9 -> V10 -> V13
    V3 -> V4 -> V24 -> V23 -> V21 -> V17 -> V16 -> V14
    V3 -> V4 -> V24 -> V23 -> V22 -> V9 -> V15
    V3 -> V4 -> V24 -> V23 -> V21 -> V17 -> V16
    V3 -> V4 -> V24 -> V23 -> V21 -> V17
    V3 -> V4 -> V24 -> V23 -> V21 -> V17 -> V18
    V3 -> V4 -> V24 -> V23 -> V21 -> V20 -> V19
    V3 -> V4 -> V24 -> V23 -> V21 -> V20
    V3 -> V4 -> V24 -> V23 -> V21
    V3 -> V4 -> V24 -> V23 -> V22
    V3 -> V4 -> V24 -> V23
    V3 -> V4 -> V24
    V3 -> V4 -> V25
    V3 -> V4 -> V24 -> V26
    V3 -> V4 -> V24 -> V26 -> V27
    V4 -> V25 -> V1
    V4 -> V3 -> V2
    V4 -> V3
    V4 -> V4
    V4 -> V5
    V4 -> V5 -> V6
    V4 -> V5 -> V6 -> V7
    V4 -> V5 -> V6 -> V7 -> V8
    V4 -> V24 -> V23 -> V22 -> V9
    V4 -> V24 -> V23 -> V22 -> V9 -> V10
    V4 -> V24 -> V23 -> V22 -> V9 -> V10 -> V11
    V4 -> V24 -> V23 -> V21 -> V17 -> V16 -> V14 -> V12
    V4 -> V24 -> V23 -> V22 -> V9 -> V10 -> V13
    V4 -> V24 -> V23 -> V21 -> V17 -> V16 -> V14
    V4 -> V24 -> V23 -> V22 -> V9 -> V15
    V4 -> V24 -> V23 -> V21 -> V17 -> V16
    V4 -> V24 -> V23 -> V21 -> V17
    V4 -> V24 -> V23 -> V21 -> V17 -> V18
    V4 -> V24 -> V23 -> V21 -> V20 -> V19
    V4 -> V24 -> V23 -> V21 -> V20
    V4 -> V24 -> V23 -> V21
    V4 -> V24 -> V23 -> V22
    V4 -> V24 -> V23
    V4 -> V24
    V4 -> V25
    V4 -> V24 -> V26
    V4 -> V24 -> V26 -> V27
    V5 -> V4 -> V25 -> V1
    V5 -> V4 -> V3 -> V2
    V5 -> V4 -> V3
    V5 -> V4
    V5 -> V5
    V5 -> V6
    V5 -> V6 -> V7
    V5 -> V6 -> V7 -> V8
    V5 -> V6 -> V7 -> V8 -> V9
    V5 -> V6 -> V7 -> V8 -> V9 -> V10
    V5 -> V6 -> V7 -> V8 -> V9 -> V10 -> V11
    V5 -> V6 -> V7 -> V8 -> V9 -> V10 -> V11 -> V12
    V5 -> V6 -> V7 -> V8 -> V9 -> V10 -> V13
    V5 -> V6 -> V7 -> V8 -> V9 -> V15 -> V14
    V5 -> V6 -> V7 -> V8 -> V9 -> V15
    V5 -> V6 -> V7 -> V8 -> V9 -> V16
    V5 -> V6 -> V23 -> V21 -> V17
    V5 -> V6 -> V23 -> V21 -> V17 -> V18
    V5 -> V6 -> V23 -> V21 -> V20 -> V19
    V5 -> V6 -> V23 -> V21 -> V20
    V5 -> V6 -> V23 -> V21
    V5 -> V6 -> V7 -> V22
    V5 -> V6 -> V23
    V5 -> V24
    V5 -> V4 -> V25
    V5 -> V24 -> V26
    V5 -> V24 -> V26 -> V27
    V6 -> V24 -> V25 -> V1
    V6 -> V5 -> V4 -> V3 -> V2
    V6 -> V5 -> V4 -> V3
    V6 -> V5 -> V4
    V6 -> V5
    V6 -> V6
    V6 -> V7
    V6 -> V7 -> V8
    V6 -> V7 -> V8 -> V9
    V6 -> V7 -> V8 -> V9 -> V10
    V6 -> V7 -> V8 -> V9 -> V10 -> V11
    V6 -> V7 -> V8 -> V9 -> V10 -> V11 -> V12
    V6 -> V7 -> V8 -> V9 -> V10 -> V13
    V6 -> V7 -> V8 -> V9 -> V15 -> V14
    V6 -> V7 -> V8 -> V9 -> V15
    V6 -> V7 -> V8 -> V9 -> V16
    V6 -> V23 -> V21 -> V17
    V6 -> V23 -> V21 -> V17 -> V18
    V6 -> V23 -> V21 -> V20 -> V19
    V6 -> V23 -> V21 -> V20
    V6 -> V23 -> V21
    V6 -> V7 -> V22
    V6 -> V23
    V6 -> V24
    V6 -> V24 -> V25
    V6 -> V23 -> V26
    V6 -> V23 -> V21 -> V27
    V7 -> V6 -> V24 -> V25 -> V1
    V7 -> V6 -> V5 -> V4 -> V3 -> V2
    V7 -> V6 -> V5 -> V4 -> V3
    V7 -> V6 -> V5 -> V4
    V7 -> V6 -> V5
    V7 -> V6
    V7 -> V7
    V7 -> V8
    V7 -> V8 -> V9
    V7 -> V8 -> V9 -> V10
    V7 -> V8 -> V9 -> V10 -> V11
    V7 -> V8 -> V9 -> V10 -> V11 -> V12
    V7 -> V8 -> V9 -> V10 -> V13
    V7 -> V8 -> V9 -> V15 -> V14
    V7 -> V8 -> V9 -> V15
    V7 -> V8 -> V9 -> V16
    V7 -> V8 -> V9 -> V17
    V7 -> V8 -> V9 -> V16 -> V18
    V7 -> V22 -> V21 -> V20 -> V19
    V7 -> V22 -> V21 -> V20
    V7 -> V22 -> V21
    V7 -> V22
    V7 -> V6 -> V23
    V7 -> V6 -> V24
    V7 -> V6 -> V24 -> V25
    V7 -> V6 -> V23 -> V26
    V7 -> V22 -> V21 -> V27
    V8 -> V7 -> V6 -> V24 -> V25 -> V1
    V8 -> V7 -> V6 -> V5 -> V4 -> V3 -> V2
    V8 -> V7 -> V6 -> V5 -> V4 -> V3
    V8 -> V7 -> V6 -> V5 -> V4
    V8 -> V7 -> V6 -> V5
    V8 -> V7 -> V6
    V8 -> V7
    V8 -> V8
    V8 -> V9
    V8 -> V9 -> V10
    V8 -> V9 -> V10 -> V11
    V8 -> V9 -> V10 -> V11 -> V12
    V8 -> V9 -> V10 -> V13
    V8 -> V9 -> V15 -> V14
    V8 -> V9 -> V15
    V8 -> V9 -> V16
    V8 -> V9 -> V17
    V8 -> V9 -> V16 -> V18
    V8 -> V9 -> V16 -> V18 -> V19
    V8 -> V22 -> V21 -> V20
    V8 -> V22 -> V21
    V8 -> V22
    V8 -> V22 -> V23
    V8 -> V7 -> V6 -> V24
    V8 -> V7 -> V6 -> V24 -> V25
    V8 -> V22 -> V23 -> V26
    V8 -> V22 -> V21 -> V27
    V9 -> V22 -> V23 -> V24 -> V25 -> V1
    V9 -> V22 -> V23 -> V24 -> V4 -> V3 -> V2
    V9 -> V22 -> V23 -> V24 -> V4 -> V3
    V9 -> V22 -> V23 -> V24 -> V4
    V9 -> V8 -> V7 -> V6 -> V5
    V9 -> V8 -> V7 -> V6
    V9 -> V8 -> V7
    V9 -> V8
    V9 -> V9
    V9 -> V10
    V9 -> V10 -> V11
    V9 -> V10 -> V11 -> V12
    V9 -> V10 -> V13
    V9 -> V15 -> V14
    V9 -> V15
    V9 -> V16
    V9 -> V17
    V9 -> V16 -> V18
    V9 -> V16 -> V18 -> V19
    V9 -> V16 -> V18 -> V20
    V9 -> V17 -> V21
    V9 -> V22
    V9 -> V22 -> V23
    V9 -> V22 -> V23 -> V24
    V9 -> V22 -> V23 -> V24 -> V25
    V9 -> V22 -> V23 -> V26
    V9 -> V17 -> V21 -> V27
    V10 -> V9 -> V22 -> V23 -> V24 -> V25 -> V1
    V10 -> V9 -> V22 -> V23 -> V24 -> V4 -> V3 -> V2
    V10 -> V9 -> V22 -> V23 -> V24 -> V4 -> V3
    V10 -> V9 -> V22 -> V23 -> V24 -> V4
    V10 -> V9 -> V8 -> V7 -> V6 -> V5
    V10 -> V9 -> V8 -> V7 -> V6
    V10 -> V9 -> V8 -> V7
    V10 -> V9 -> V8
    V10 -> V9
    V10 -> V10
    V10 -> V11
    V10 -> V11 -> V12
    V10 -> V13
    V10 -> V13 -> V14
    V10 -> V15
    V10 -> V9 -> V16
    V10 -> V9 -> V17
    V10 -> V9 -> V16 -> V18
    V10 -> V9 -> V16 -> V18 -> V19
    V10 -> V9 -> V16 -> V18 -> V20
    V10 -> V9 -> V17 -> V21
    V10 -> V9 -> V22
    V10 -> V9 -> V22 -> V23
    V10 -> V9 -> V22 -> V23 -> V24
    V10 -> V9 -> V22 -> V23 -> V24 -> V25
    V10 -> V9 -> V22 -> V23 -> V26
    V10 -> V9 -> V17 -> V21 -> V27
    V11 -> V10 -> V9 -> V22 -> V23 -> V24 -> V25 -> V1
    V11 -> V10 -> V9 -> V22 -> V23 -> V24 -> V4 -> V3 -> V2
    V11 -> V10 -> V9 -> V22 -> V23 -> V24 -> V4 -> V3
    V11 -> V10 -> V9 -> V22 -> V23 -> V24 -> V4
    V11 -> V10 -> V9 -> V8 -> V7 -> V6 -> V5
    V11 -> V10 -> V9 -> V8 -> V7 -> V6
    V11 -> V10 -> V9 -> V8 -> V7
    V11 -> V10 -> V9 -> V8
    V11 -> V10 -> V9
    V11 -> V10
    V11 -> V11
    V11 -> V12
    V11 -> V13
    V11 -> V12 -> V14
    V11 -> V10 -> V15
    V11 -> V10 -> V9 -> V16
    V11 -> V10 -> V9 -> V17
    V11 -> V10 -> V9 -> V16 -> V18
    V11 -> V10 -> V9 -> V16 -> V18 -> V19
    V11 -> V10 -> V9 -> V16 -> V18 -> V20
    V11 -> V10 -> V9 -> V17 -> V21
    V11 -> V10 -> V9 -> V22
    V11 -> V10 -> V9 -> V22 -> V23
    V11 -> V10 -> V9 -> V22 -> V23 -> V24
    V11 -> V10 -> V9 -> V22 -> V23 -> V24 -> V25
    V11 -> V10 -> V9 -> V22 -> V23 -> V26
    V11 -> V10 -> V9 -> V17 -> V21 -> V27
    V12 -> V14 -> V16 -> V17 -> V21 -> V23 -> V24 -> V25 -> V1
    V12 -> V14 -> V16 -> V17 -> V21 -> V23 -> V24 -> V4 -> V3 -> V2
    V12 -> V14 -> V16 -> V17 -> V21 -> V23 -> V24 -> V4 -> V3
    V12 -> V14 -> V16 -> V17 -> V21 -> V23 -> V24 -> V4
    V12 -> V11 -> V10 -> V9 -> V8 -> V7 -> V6 -> V5
    V12 -> V11 -> V10 -> V9 -> V8 -> V7 -> V6
    V12 -> V11 -> V10 -> V9 -> V8 -> V7
    V12 -> V11 -> V10 -> V9 -> V8
    V12 -> V11 -> V10 -> V9
    V12 -> V11 -> V10
    V12 -> V11
    V12 -> V12
    V12 -> V13
    V12 -> V14
    V12 -> V13 -> V15
    V12 -> V14 -> V16
    V12 -> V14 -> V16 -> V17
    V12 -> V14 -> V16 -> V18
    V12 -> V14 -> V16 -> V18 -> V19
    V12 -> V14 -> V16 -> V18 -> V20
    V12 -> V14 -> V16 -> V17 -> V21
    V12 -> V11 -> V10 -> V9 -> V22
    V12 -> V14 -> V16 -> V17 -> V21 -> V23
    V12 -> V14 -> V16 -> V17 -> V21 -> V23 -> V24
    V12 -> V14 -> V16 -> V17 -> V21 -> V23 -> V24 -> V25
    V12 -> V14 -> V16 -> V17 -> V21 -> V23 -> V26
    V12 -> V14 -> V16 -> V17 -> V21 -> V27
    V13 -> V10 -> V9 -> V22 -> V23 -> V24 -> V25 -> V1
    V13 -> V10 -> V9 -> V22 -> V23 -> V24 -> V4 -> V3 -> V2
    V13 -> V10 -> V9 -> V22 -> V23 -> V24 -> V4 -> V3
    V13 -> V10 -> V9 -> V22 -> V23 -> V24 -> V4
    V13 -> V10 -> V9 -> V8 -> V7 -> V6 -> V5
    V13 -> V10 -> V9 -> V8 -> V7 -> V6
    V13 -> V10 -> V9 -> V8 -> V7
    V13 -> V10 -> V9 -> V8
    V13 -> V10 -> V9
    V13 -> V10
    V13 -> V11
    V13 -> V12
    V13 -> V13
    V13 -> V14
    V13 -> V15
    V13 -> V14 -> V16
    V13 -> V10 -> V9 -> V17
    V13 -> V14 -> V16 -> V18
    V13 -> V14 -> V16 -> V18 -> V19
    V13 -> V14 -> V16 -> V18 -> V20
    V13 -> V10 -> V9 -> V17 -> V21
    V13 -> V10 -> V9 -> V22
    V13 -> V10 -> V9 -> V22 -> V23
    V13 -> V10 -> V9 -> V22 -> V23 -> V24
    V13 -> V10 -> V9 -> V22 -> V23 -> V24 -> V25
    V13 -> V10 -> V9 -> V22 -> V23 -> V26
    V13 -> V10 -> V9 -> V17 -> V21 -> V27
    V14 -> V16 -> V17 -> V21 -> V23 -> V24 -> V25 -> V1
    V14 -> V16 -> V17 -> V21 -> V23 -> V24 -> V4 -> V3 -> V2
    V14 -> V16 -> V17 -> V21 -> V23 -> V24 -> V4 -> V3
    V14 -> V16 -> V17 -> V21 -> V23 -> V24 -> V4
    V14 -> V15 -> V9 -> V8 -> V7 -> V6 -> V5
    V14 -> V15 -> V9 -> V8 -> V7 -> V6
    V14 -> V15 -> V9 -> V8 -> V7
    V14 -> V15 -> V9 -> V8
    V14 -> V15 -> V9
    V14 -> V13 -> V10
    V14 -> V12 -> V11
    V14 -> V12
    V14 -> V13
    V14 -> V14
    V14 -> V15
    V14 -> V16
    V14 -> V16 -> V17
    V14 -> V16 -> V18
    V14 -> V16 -> V18 -> V19
    V14 -> V16 -> V18 -> V20
    V14 -> V16 -> V17 -> V21
    V14 -> V15 -> V9 -> V22
    V14 -> V16 -> V17 -> V21 -> V23
    V14 -> V16 -> V17 -> V21 -> V23 -> V24
    V14 -> V16 -> V17 -> V21 -> V23 -> V24 -> V25
    V14 -> V16 -> V17 -> V21 -> V23 -> V26
    V14 -> V16 -> V17 -> V21 -> V27
    V15 -> V9 -> V22 -> V23 -> V24 -> V25 -> V1
    V15 -> V9 -> V22 -> V23 -> V24 -> V4 -> V3 -> V2
    V15 -> V9 -> V22 -> V23 -> V24 -> V4 -> V3
    V15 -> V9 -> V22 -> V23 -> V24 -> V4
    V15 -> V9 -> V8 -> V7 -> V6 -> V5
    V15 -> V9 -> V8 -> V7 -> V6
    V15 -> V9 -> V8 -> V7
    V15 -> V9 -> V8
    V15 -> V9
    V15 -> V10
    V15 -> V10 -> V11
    V15 -> V13 -> V12
    V15 -> V13
    V15 -> V14
    V15 -> V15
    V15 -> V16
    V15 -> V9 -> V17
    V15 -> V16 -> V18
    V15 -> V16 -> V18 -> V19
    V15 -> V16 -> V18 -> V20
    V15 -> V9 -> V17 -> V21
    V15 -> V9 -> V22
    V15 -> V9 -> V22 -> V23
    V15 -> V9 -> V22 -> V23 -> V24
    V15 -> V9 -> V22 -> V23 -> V24 -> V25
    V15 -> V9 -> V22 -> V23 -> V26
    V15 -> V9 -> V17 -> V21 -> V27
    V16 -> V17 -> V21 -> V23 -> V24 -> V25 -> V1
    V16 -> V17 -> V21 -> V23 -> V24 -> V4 -> V3 -> V2
    V16 -> V17 -> V21 -> V23 -> V24 -> V4 -> V3
    V16 -> V17 -> V21 -> V23 -> V24 -> V4
    V16 -> V9 -> V8 -> V7 -> V6 -> V5
    V16 -> V9 -> V8 -> V7 -> V6
    V16 -> V9 -> V8 -> V7
    V16 -> V9 -> V8
    V16 -> V9
    V16 -> V9 -> V10
    V16 -> V9 -> V10 -> V11
    V16 -> V14 -> V12
    V16 -> V14 -> V13
    V16 -> V14
    V16 -> V15
    V16 -> V16
    V16 -> V17
    V16 -> V18
    V16 -> V18 -> V19
    V16 -> V18 -> V20
    V16 -> V17 -> V21
    V16 -> V9 -> V22
    V16 -> V17 -> V21 -> V23
    V16 -> V17 -> V21 -> V23 -> V24
    V16 -> V17 -> V21 -> V23 -> V24 -> V25
    V16 -> V17 -> V21 -> V23 -> V26
    V16 -> V17 -> V21 -> V27
    V17 -> V21 -> V23 -> V24 -> V25 -> V1
    V17 -> V21 -> V23 -> V24 -> V4 -> V3 -> V2
    V17 -> V21 -> V23 -> V24 -> V4 -> V3
    V17 -> V21 -> V23 -> V24 -> V4
    V17 -> V21 -> V23 -> V6 -> V5
    V17 -> V21 -> V23 -> V6
    V17 -> V9 -> V8 -> V7
    V17 -> V9 -> V8
    V17 -> V9
    V17 -> V9 -> V10
    V17 -> V9 -> V10 -> V11
    V17 -> V16 -> V14 -> V12
    V17 -> V9 -> V10 -> V13
    V17 -> V16 -> V14
    V17 -> V9 -> V15
    V17 -> V16
    V17 -> V17
    V17 -> V18
    V17 -> V18 -> V19
    V17 -> V18 -> V20
    V17 -> V21
    V17 -> V9 -> V22
    V17 -> V21 -> V23
    V17 -> V21 -> V23 -> V24
    V17 -> V21 -> V23 -> V24 -> V25
    V17 -> V21 -> V23 -> V26
    V17 -> V21 -> V27
    V18 -> V17 -> V21 -> V23 -> V24 -> V25 -> V1
    V18 -> V17 -> V21 -> V23 -> V24 -> V4 -> V3 -> V2
    V18 -> V17 -> V21 -> V23 -> V24 -> V4 -> V3
    V18 -> V17 -> V21 -> V23 -> V24 -> V4
    V18 -> V17 -> V21 -> V23 -> V6 -> V5
    V18 -> V17 -> V21 -> V23 -> V6
    V18 -> V16 -> V9 -> V8 -> V7
    V18 -> V16 -> V9 -> V8
    V18 -> V16 -> V9
    V18 -> V16 -> V9 -> V10
    V18 -> V16 -> V9 -> V10 -> V11
    V18 -> V16 -> V14 -> V12
    V18 -> V16 -> V14 -> V13
    V18 -> V16 -> V14
    V18 -> V16 -> V15
    V18 -> V16
    V18 -> V17
    V18 -> V18
    V18 -> V19
    V18 -> V20
    V18 -> V17 -> V21
    V18 -> V16 -> V9 -> V22
    V18 -> V17 -> V21 -> V23
    V18 -> V17 -> V21 -> V23 -> V24
    V18 -> V17 -> V21 -> V23 -> V24 -> V25
    V18 -> V17 -> V21 -> V23 -> V26
    V18 -> V17 -> V21 -> V27
    V19 -> V20 -> V21 -> V23 -> V24 -> V25 -> V1
    V19 -> V20 -> V21 -> V23 -> V24 -> V4 -> V3 -> V2
    V19 -> V20 -> V21 -> V23 -> V24 -> V4 -> V3
    V19 -> V20 -> V21 -> V23 -> V24 -> V4
    V19 -> V20 -> V21 -> V23 -> V6 -> V5
    V19 -> V20 -> V21 -> V23 -> V6
    V19 -> V20 -> V21 -> V22 -> V7
    V19 -> V18 -> V16 -> V9 -> V8
    V19 -> V18 -> V16 -> V9
    V19 -> V18 -> V16 -> V9 -> V10
    V19 -> V18 -> V16 -> V9 -> V10 -> V11
    V19 -> V18 -> V16 -> V14 -> V12
    V19 -> V18 -> V16 -> V14 -> V13
    V19 -> V18 -> V16 -> V14
    V19 -> V18 -> V16 -> V15
    V19 -> V18 -> V16
    V19 -> V18 -> V17
    V19 -> V18
    V19 -> V19
    V19 -> V20
    V19 -> V20 -> V21
    V19 -> V20 -> V21 -> V22
    V19 -> V20 -> V21 -> V23
    V19 -> V20 -> V21 -> V23 -> V24
    V19 -> V20 -> V21 -> V23 -> V24 -> V25
    V19 -> V20 -> V21 -> V23 -> V26
    V19 -> V20 -> V21 -> V27
    V20 -> V21 -> V23 -> V24 -> V25 -> V1
    V20 -> V21 -> V23 -> V24 -> V4 -> V3 -> V2
    V20 -> V21 -> V23 -> V24 -> V4 -> V3
    V20 -> V21 -> V23 -> V24 -> V4
    V20 -> V21 -> V23 -> V6 -> V5
    V20 -> V21 -> V23 -> V6
    V20 -> V21 -> V22 -> V7
    V20 -> V21 -> V22 -> V8
    V20 -> V18 -> V16 -> V9
    V20 -> V18 -> V16 -> V9 -> V10
    V20 -> V18 -> V16 -> V9 -> V10 -> V11
    V20 -> V18 -> V16 -> V14 -> V12
    V20 -> V18 -> V16 -> V14 -> V13
    V20 -> V18 -> V16 -> V14
    V20 -> V18 -> V16 -> V15
    V20 -> V18 -> V16
    V20 -> V18 -> V17
    V20 -> V18
    V20 -> V19
    V20 -> V20
    V20 -> V21
    V20 -> V21 -> V22
    V20 -> V21 -> V23
    V20 -> V21 -> V23 -> V24
    V20 -> V21 -> V23 -> V24 -> V25
    V20 -> V21 -> V23 -> V26
    V20 -> V21 -> V27
    V21 -> V23 -> V24 -> V25 -> V1
    V21 -> V23 -> V24 -> V4 -> V3 -> V2
    V21 -> V23 -> V24 -> V4 -> V3
    V21 -> V23 -> V24 -> V4
    V21 -> V23 -> V6 -> V5
    V21 -> V23 -> V6
    V21 -> V22 -> V7
    V21 -> V22 -> V8
    V21 -> V17 -> V9
    V21 -> V17 -> V9 -> V10
    V21 -> V17 -> V9 -> V10 -> V11
    V21 -> V17 -> V16 -> V14 -> V12
    V21 -> V17 -> V9 -> V10 -> V13
    V21 -> V17 -> V16 -> V14
    V21 -> V17 -> V9 -> V15
    V21 -> V17 -> V16
    V21 -> V17
    V21 -> V17 -> V18
    V21 -> V20 -> V19
    V21 -> V20
    V21 -> V21
    V21 -> V22
    V21 -> V23
    V21 -> V23 -> V24
    V21 -> V23 -> V24 -> V25
    V21 -> V23 -> V26
    V21 -> V27
    V22 -> V23 -> V24 -> V25 -> V1
    V22 -> V23 -> V24 -> V4 -> V3 -> V2
    V22 -> V23 -> V24 -> V4 -> V3
    V22 -> V23 -> V24 -> V4
    V22 -> V7 -> V6 -> V5
    V22 -> V7 -> V6
    V22 -> V7
    V22 -> V8
    V22 -> V9
    V22 -> V9 -> V10
    V22 -> V9 -> V10 -> V11
    V22 -> V9 -> V10 -> V11 -> V12
    V22 -> V9 -> V10 -> V13
    V22 -> V9 -> V15 -> V14
    V22 -> V9 -> V15
    V22 -> V9 -> V16
    V22 -> V9 -> V17
    V22 -> V9 -> V16 -> V18
    V22 -> V21 -> V20 -> V19
    V22 -> V21 -> V20
    V22 -> V21
    V22 -> V22
    V22 -> V23
    V22 -> V23 -> V24
    V22 -> V23 -> V24 -> V25
    V22 -> V23 -> V26
    V22 -> V21 -> V27
    V23 -> V24 -> V25 -> V1
    V23 -> V24 -> V4 -> V3 -> V2
    V23 -> V24 -> V4 -> V3
    V23 -> V24 -> V4
    V23 -> V6 -> V5
    V23 -> V6
    V23 -> V6 -> V7
    V23 -> V22 -> V8
    V23 -> V22 -> V9
    V23 -> V22 -> V9 -> V10
    V23 -> V22 -> V9 -> V10 -> V11
    V23 -> V21 -> V17 -> V16 -> V14 -> V12
    V23 -> V22 -> V9 -> V10 -> V13
    V23 -> V21 -> V17 -> V16 -> V14
    V23 -> V22 -> V9 -> V15
    V23 -> V21 -> V17 -> V16
    V23 -> V21 -> V17
    V23 -> V21 -> V17 -> V18
    V23 -> V21 -> V20 -> V19
    V23 -> V21 -> V20
    V23 -> V21
    V23 -> V22
    V23 -> V23
    V23 -> V24
    V23 -> V24 -> V25
    V23 -> V26
    V23 -> V21 -> V27
    V24 -> V25 -> V1
    V24 -> V4 -> V3 -> V2
    V24 -> V4 -> V3
    V24 -> V4
    V24 -> V5
    V24 -> V6
    V24 -> V6 -> V7
    V24 -> V6 -> V7 -> V8
    V24 -> V23 -> V22 -> V9
    V24 -> V23 -> V22 -> V9 -> V10
    V24 -> V23 -> V22 -> V9 -> V10 -> V11
    V24 -> V23 -> V21 -> V17 -> V16 -> V14 -> V12
    V24 -> V23 -> V22 -> V9 -> V10 -> V13
    V24 -> V23 -> V21 -> V17 -> V16 -> V14
    V24 -> V23 -> V22 -> V9 -> V15
    V24 -> V23 -> V21 -> V17 -> V16
    V24 -> V23 -> V21 -> V17
    V24 -> V23 -> V21 -> V17 -> V18
    V24 -> V23 -> V21 -> V20 -> V19
    V24 -> V23 -> V21 -> V20
    V24 -> V23 -> V21
    V24 -> V23 -> V22
    V24 -> V23
    V24 -> V24
    V24 -> V25
    V24 -> V26
    V24 -> V26 -> V27
    V25 -> V1
    V25 -> V1 -> V2
    V25 -> V3
    V25 -> V4
    V25 -> V4 -> V5
    V25 -> V24 -> V6
    V25 -> V24 -> V6 -> V7
    V25 -> V24 -> V6 -> V7 -> V8
    V25 -> V24 -> V23 -> V22 -> V9
    V25 -> V24 -> V23 -> V22 -> V9 -> V10
    V25 -> V24 -> V23 -> V22 -> V9 -> V10 -> V11
    V25 -> V24 -> V23 -> V21 -> V17 -> V16 -> V14 -> V12
    V25 -> V24 -> V23 -> V22 -> V9 -> V10 -> V13
    V25 -> V24 -> V23 -> V21 -> V17 -> V16 -> V14
    V25 -> V24 -> V23 -> V22 -> V9 -> V15
    V25 -> V24 -> V23 -> V21 -> V17 -> V16
    V25 -> V24 -> V23 -> V21 -> V17
    V25 -> V24 -> V23 -> V21 -> V17 -> V18
    V25 -> V24 -> V23 -> V21 -> V20 -> V19
    V25 -> V24 -> V23 -> V21 -> V20
    V25 -> V24 -> V23 -> V21
    V25 -> V24 -> V23 -> V22
    V25 -> V24 -> V23
    V25 -> V24
    V25 -> V25
    V25 -> V26
    V25 -> V26 -> V27
    V26 -> V25 -> V1
    V26 -> V25 -> V1 -> V2
    V26 -> V25 -> V3
    V26 -> V24 -> V4
    V26 -> V24 -> V5
    V26 -> V23 -> V6
    V26 -> V23 -> V6 -> V7
    V26 -> V23 -> V22 -> V8
    V26 -> V23 -> V22 -> V9
    V26 -> V23 -> V22 -> V9 -> V10
    V26 -> V23 -> V22 -> V9 -> V10 -> V11
    V26 -> V23 -> V21 -> V17 -> V16 -> V14 -> V12
    V26 -> V23 -> V22 -> V9 -> V10 -> V13
    V26 -> V23 -> V21 -> V17 -> V16 -> V14
    V26 -> V23 -> V22 -> V9 -> V15
    V26 -> V23 -> V21 -> V17 -> V16
    V26 -> V23 -> V21 -> V17
    V26 -> V23 -> V21 -> V17 -> V18
    V26 -> V23 -> V21 -> V20 -> V19
    V26 -> V23 -> V21 -> V20
    V26 -> V23 -> V21
    V26 -> V23 -> V22
    V26 -> V23
    V26 -> V24
    V26 -> V25
    V26 -> V26
    V26 -> V27
    V27 -> V26 -> V25 -> V1
    V27 -> V26 -> V25 -> V1 -> V2
    V27 -> V26 -> V25 -> V3
    V27 -> V26 -> V24 -> V4
    V27 -> V26 -> V24 -> V5
    V27 -> V21 -> V23 -> V6
    V27 -> V21 -> V22 -> V7
    V27 -> V21 -> V22 -> V8
    V27 -> V21 -> V17 -> V9
    V27 -> V21 -> V17 -> V9 -> V10
    V27 -> V21 -> V17 -> V9 -> V10 -> V11
    V27 -> V21 -> V17 -> V16 -> V14 -> V12
    V27 -> V21 -> V17 -> V9 -> V10 -> V13
    V27 -> V21 -> V17 -> V16 -> V14
    V27 -> V21 -> V17 -> V9 -> V15
    V27 -> V21 -> V17 -> V16
    V27 -> V21 -> V17
    V27 -> V21 -> V17 -> V18
    V27 -> V21 -> V20 -> V19
    V27 -> V21 -> V20
    V27 -> V21
    V27 -> V21 -> V22
    V27 -> V21 -> V23
    V27 -> V26 -> V24
    V27 -> V26 -> V25
    V27 -> V26
    V27 -> V27