Поиск всех путей на графе (Небольшой тест. Часть 2)

 == Идем по строке ====a Добавим новый индекс (конкатенация):  - a ->  Индексу newdot: ->  b Печатаем массив ways после всех итерций третьего цикла Array
(
    [a] => Array
        (
            [a] => 0
        )

    [b] => Array
        (
            [ab] => 3
        )

)

 Новая итерация второго цикла Добавим новый индекс (конкатенация):  - a ->  Индексу newdot: ->  c Печатаем массив ways после всех итерций третьего цикла Array
(
    [a] => Array
        (
            [a] => 0
        )

    [b] => Array
        (
            [ab] => 3
        )

    [c] => Array
        (
            [ac] => 7
        )

)

 Новая итерация второго цикла Добавим новый индекс (конкатенация):  - a ->  Индексу newdot: ->  d Печатаем массив ways после всех итерций третьего цикла Array
(
    [a] => Array
        (
            [a] => 0
        )

    [b] => Array
        (
            [ab] => 3
        )

    [c] => Array
        (
            [ac] => 7
        )

    [d] => Array
        (
            [ad] => 2
        )

)

 Новая итерация второго цикла Добавим новый индекс (конкатенация):  - a ->  Индексу newdot: ->  f Печатаем массив ways после всех итерций третьего цикла Array
(
    [a] => Array
        (
            [a] => 0
        )

    [b] => Array
        (
            [ab] => 3
        )

    [c] => Array
        (
            [ac] => 7
        )

    [d] => Array
        (
            [ad] => 2
        )

    [f] => Array
        (
            [af] => 119
        )

)

 Новая итерация второго цикла  == Идем по столбцу вниз====>\r\n  возврат в первый цикл  == Идем по строке ====b Добавим новый индекс (конкатенация):  - ab ->  Индексу newdot: ->  d Печатаем массив ways после всех итерций третьего цикла Array
(
    [a] => Array
        (
            [a] => 0
        )

    [b] => Array
        (
            [ab] => 3
        )

    [c] => Array
        (
            [ac] => 7
        )

    [d] => Array
        (
            [ad] => 2
            [abd] => 7
        )

    [f] => Array
        (
            [af] => 119
        )

)

 Новая итерация второго цикла Добавим новый индекс (конкатенация):  - ab ->  Индексу newdot: ->  e Печатаем массив ways после всех итерций третьего цикла Array
(
    [a] => Array
        (
            [a] => 0
        )

    [b] => Array
        (
            [ab] => 3
        )

    [c] => Array
        (
            [ac] => 7
        )

    [d] => Array
        (
            [ad] => 2
            [abd] => 7
        )

    [f] => Array
        (
            [af] => 119
        )

    [e] => Array
        (
            [abe] => 9
        )

)

 Новая итерация второго цикла Добавим новый индекс (конкатенация):  - ab ->  Индексу newdot: ->  f Печатаем массив ways после всех итерций третьего цикла Array
(
    [a] => Array
        (
            [a] => 0
        )

    [b] => Array
        (
            [ab] => 3
        )

    [c] => Array
        (
            [ac] => 7
        )

    [d] => Array
        (
            [ad] => 2
            [abd] => 7
        )

    [f] => Array
        (
            [af] => 119
            [abf] => 11
        )

    [e] => Array
        (
            [abe] => 9
        )

)

 Новая итерация второго цикла  == Идем по столбцу вниз====>\r\n  возврат в первый цикл  == Идем по строке ====c Добавим новый индекс (конкатенация):  - ac ->  Индексу newdot: ->  d Печатаем массив ways после всех итерций третьего цикла Array
(
    [a] => Array
        (
            [a] => 0
        )

    [b] => Array
        (
            [ab] => 3
        )

    [c] => Array
        (
            [ac] => 7
        )

    [d] => Array
        (
            [ad] => 2
            [abd] => 7
            [acd] => 12
        )

    [f] => Array
        (
            [af] => 119
            [abf] => 11
        )

    [e] => Array
        (
            [abe] => 9
        )

)

 Новая итерация второго цикла Добавим новый индекс (конкатенация):  - ac ->  Индексу newdot: ->  e Печатаем массив ways после всех итерций третьего цикла Array
(
    [a] => Array
        (
            [a] => 0
        )

    [b] => Array
        (
            [ab] => 3
        )

    [c] => Array
        (
            [ac] => 7
        )

    [d] => Array
        (
            [ad] => 2
            [abd] => 7
            [acd] => 12
        )

    [f] => Array
        (
            [af] => 119
            [abf] => 11
        )

    [e] => Array
        (
            [abe] => 9
            [ace] => 10
        )

)

 Новая итерация второго цикла Добавим новый индекс (конкатенация):  - ac ->  Индексу newdot: ->  f Печатаем массив ways после всех итерций третьего цикла Array
(
    [a] => Array
        (
            [a] => 0
        )

    [b] => Array
        (
            [ab] => 3
        )

    [c] => Array
        (
            [ac] => 7
        )

    [d] => Array
        (
            [ad] => 2
            [abd] => 7
            [acd] => 12
        )

    [f] => Array
        (
            [af] => 119
            [abf] => 11
            [acf] => 9
        )

    [e] => Array
        (
            [abe] => 9
            [ace] => 10
        )

)

 Новая итерация второго цикла  == Идем по столбцу вниз====>\r\n  возврат в первый цикл  == Идем по строке ====d Добавим новый индекс (конкатенация):  - ad ->  Индексу newdot: ->  eДобавим новый индекс (конкатенация):  - abd ->  Индексу newdot: ->  eДобавим новый индекс (конкатенация):  - acd ->  Индексу newdot: ->  e Печатаем массив ways после всех итерций третьего цикла Array
(
    [a] => Array
        (
            [a] => 0
        )

    [b] => Array
        (
            [ab] => 3
        )

    [c] => Array
        (
            [ac] => 7
        )

    [d] => Array
        (
            [ad] => 2
            [abd] => 7
            [acd] => 12
        )

    [f] => Array
        (
            [af] => 119
            [abf] => 11
            [acf] => 9
        )

    [e] => Array
        (
            [abe] => 9
            [ace] => 10
            [ade] => 9
            [abde] => 14
            [acde] => 19
        )

)

 Новая итерация второго цикла Добавим новый индекс (конкатенация):  - ad ->  Индексу newdot: ->  fДобавим новый индекс (конкатенация):  - abd ->  Индексу newdot: ->  fДобавим новый индекс (конкатенация):  - acd ->  Индексу newdot: ->  f Печатаем массив ways после всех итерций третьего цикла Array
(
    [a] => Array
        (
            [a] => 0
        )

    [b] => Array
        (
            [ab] => 3
        )

    [c] => Array
        (
            [ac] => 7
        )

    [d] => Array
        (
            [ad] => 2
            [abd] => 7
            [acd] => 12
        )

    [f] => Array
        (
            [af] => 119
            [abf] => 11
            [acf] => 9
            [adf] => 6
            [abdf] => 11
            [acdf] => 16
        )

    [e] => Array
        (
            [abe] => 9
            [ace] => 10
            [ade] => 9
            [abde] => 14
            [acde] => 19
        )

)

<?php
$links = array(
    'a' => array('b' => 3, 'c' => 7, 'd' => 2, 'f' => 119),
    'b' => array('d' => 4, 'e' => 6, 'f' => 8),
    'c' => array('d' => 5, 'e' => 3, 'f' => 2),
    'd' => array('e' => 7, 'f' => 4),
    'e' => array('f' => 3),
    'f' => array(),
);

$from = 'a';
$to = 'f';

$i = 0;
/* если нужен список путей */
$ways = array($from => array($from => 0));

foreach ($links as $dot => $list) {
    $i++;
    print ' == Идем по строке ====';
    echo $dot . ' ';
    if (!isset($ways[$dot])) continue;
    $curways = $ways[$dot]; // пути до текущей точки

    foreach ($list as $newdot => $dist) {
        foreach ($curways as $way => $waydist) {
            echo "Добавим новый индекс (конкатенация): ";
            echo ' - ' . $way . ' -> ';
            $ways[$newdot][$way . $newdot] = $waydist + $dist;
            echo " Индексу newdot: ->  " . $newdot;
        }
        print ' Печатаем массив ways после всех итерций третьего цикла ';
        print_r($ways);
        print "\n";
        print " Новая итерация второго цикла ";
    }

    print ' == Идем по столбцу вниз====>';
    print '  возврат в первый цикл ';
}
?>

Не надо об этом думать, 

#!/usr/bin/env lua

local input =
[[
a → b, c, d, z
b → d, e, f, z
c → d, e, f, z
d → e, f, z
e → f, z
f → g, h, j, z
g → h, i, j, z
h → i, j, k, z
i → j, k, l, z
j → k, m, z
k → l, n, o, z
l → m, z
m → n, o, z
n → o, z
o → p, z
p → q, z
q → r, z
r → s, z
s → t, u, z
t → u, v, z
u → v, w, z
v → w, z
w → x, y, z
x → y, z
y → z
z → (нет исходящих)
]]

local paths = { }

for start,list,val in input:gmatch('(%w)%s+→(.-)\n') do
    paths[start] = { }
    for v in list:gmatch('%s+(%w)') do
        if not paths[start][v] then
           paths[start][v] = v
        end
    end
    ---
    for k, p in pairs(paths) do
        for x,v in pairs(p) do
            if x == start  then
               p[x] = paths[start]
            end
        end
    end
end

local count = 0

local function trace(path,name)
    for k,v in pairs(path) do
        if k == 'z' then
           io.write(name..'z \n')
           count = count + 1
        else
           trace(v,name..k..' -> ')
        end
    end
end

trace(paths['a'],'')
print(count)

...
22061

real	0m1,442s
user	0m0,373s
sys	0m0,435s

scheme@(hello-lor)> ,time (define pz (list-paths "z"))
;; 0.006063s real time, 0.006021s run time.  0.000000s spent in GC.
scheme@(hello-lor)> (length pz)
$46 = 22061

На всякий вопрос найдётся ответ.
У нас есть TCO, у вас его нет.

#include <stdio.h>
#include <string.h>

/* Максимальное количество вершин в пути.
   Граф небольшой, 20 достаточно с запасом. */
#define MAX_PATH 20

/* Функция возвращает указатель на массив соседей для данной вершины.
   Вершины: 'a'..'f'. Возвращает NULL для неверной вершины. */
static const char *get_neighbors(char v) {
    switch (v) {
        case 'a': return "bcd";
        case 'b': return "def";
        case 'c': return "def";
        case 'd': return "ef";
        case 'e': return "f";
        case 'f': return "";
        default:  return NULL;
    }
}

/* Вспомогательная функция: найти индекс символа в строке.
   Возвращает -1, если не найден. */
static int str_index_of(const char *s, char c) {
    int i = 0;
    while (s[i] != '\0') {
        if (s[i] == c) return i;
        i++;
    }
    return -1;
}

int main(void) {
    /* Первый путь (из PHP-скрипта) */
    char path[MAX_PATH];
    int path_len = 0;

    /* Инициализация первого пути: a -> b -> d -> e -> f */
    path[path_len++] = 'a';
    path[path_len++] = 'b';
    path[path_len++] = 'd';
    path[path_len++] = 'e';
    path[path_len++] = 'f';

    /* Вывод первого маршрута */
    {
        int i;
        for (i = 0; i < path_len; i++) {
            if (i > 0) printf(", ");
            printf("%c", path[i]);
        }
        printf("\n");
    }

    int j = path_len - 1;

    while (j != 0) {
        char current_v = path[j - 1];
        const char *neighbors = get_neighbors(current_v);

        /* В PHP: $ar = search_val($x, $j, $arr); */
        /* Здесь neighbors — это аналог $ar */

        int key = str_index_of(neighbors, path[j]);

        /* if (isset($ar[$key + 1])) */
        if ((key != -1) && (neighbors[key + 1] != '\0')) {
            /* $x = array_slice($x, 0, $j); */
            path_len = j;

            /* array_push($x, $ar[$key + 1]); */
            path[path_len++] = neighbors[key + 1];

            /* Достраиваем путь до 'f', всегда беря первого (нулевого) соседа */
            while (1) {
                char last_v = path[path_len - 1];
                if (last_v == 'f') {
                    break;
                }
                const char *next_neighbors = get_neighbors(last_v);
                /* В PHP: search_new_val_for_push_int_x(...)[0] */
                if (next_neighbors[0] != '\0') {
                    path[path_len++] = next_neighbors[0];
                } else {
                    /* Если нет соседей, а мы не в 'f', дальше идти некуда.
                       В логике PHP это не обрабатывается явно, но предотвратим зацикливание. */
                    break;
                }
            }

            j = path_len;

            /* print_r($x); */
            {
                int i;
                for (i = 0; i < path_len; i++) {
                    if (i > 0) printf(", ");
                    printf("%c", path[i]);
                }
                printf("\n");
            }
        }

        j--;
    }

    return 0;
}

 <?php
$links = array(
    'a' => array('b' => 3, 'c' => 7, 'd' => 2, 'f' => 119),
    'b' => array('d' => 4, 'e' => 6, 'f' => 8),
    'c' => array('d' => 5, 'e' => 3, 'f' => 2),
    'd' => array('e' => 7, 'f' => 4),
    'e' => array('f' => 3),
    'f' => array(),
);

$from = 'a';
$to = 'f';

/* если нужен список путей */
$ways = array($from => array($from => 0));

foreach ($links as $dot => $list) {


    if (!isset($ways[$dot])) continue;
    $curways = $ways[$dot]; // пути до текущей точки

    foreach ($list as $newdot => $dist) {
        foreach ($curways as $way => $waydist) {

            $ways[$newdot][$way . $newdot] = $waydist + $dist;

        }
    }
}
print_r($ways);
 ?>

Важно сразу прояснить: C89 (ISO/IEC 9899:1989) не поддерживает ассоциативные массивы, динамические структуры данных произвольной формы и строковые ключи, которые активно используются в вашем PHP‑коде.

В PHP $links — это ассоциативный массив, где ключи — буквы ('a', 'b' и т. д.), а значения — вложенные ассоциативные массивы. В C89 такой структуры «из коробки» нет.

Поэтому «переписать код один в один» невозможно. Вместо этого мы реализуем эквивалентную логику на C89, используя:

    фиксированные индексы для узлов (сопоставим 'a' → 0, 'b' → 1, …, 'f' → 5);

    статическую матрицу смежности для хранения графа;

    структуры для хранения путей и расстояний.

Ниже — полная реализация на C89.

#include <stdio.h>
#include <string.h>

/* Максимальное количество узлов (a-f = 6 узлов) */
#define MAX_NODES 6
/* Максимальная длина строки пути (каждый узел - 1 символ + '\0') */
#define MAX_PATH_LEN 32

/* Структура для хранения одного варианта пути до узла */
typedef struct {
    char path[MAX_PATH_LEN];
    int distance;
} WayEntry;

/* Структура для списка путей до конкретного узла */
typedef struct {
    WayEntry entries[MAX_NODES * MAX_NODES]; /* Достаточно большое хранилище */
    int count;
} WaysList;

/* Глобальная структура для хранения всех путей ко всем узлам */
WaysList all_ways[MAX_NODES];

/* Вспомогательная функция для получения индекса по символу ('a' -> 0, 'b' -> 1...) */
int char_to_index(char c) {
    return c - 'a';
}

/* Вспомогательная функция для получения символа по индексу */
char index_to_char(int i) {
    return 'a' + i;
}

int main(void) {
    /*
       Инициализация графа.
       links[i][j] хранит расстояние от узла i до узла j.
       0 означает отсутствие прямого соединения (так как веса > 0).
    */
    int links[MAX_NODES][MAX_NODES] = {0};

    /* Заполнение данными из PHP-массива */
    /* 'a' => array('b' => 3, 'c' => 7, 'd' => 2, 'f' => 119) */
    links[char_to_index('a')][char_to_index('b')] = 3;
    links[char_to_index('a')][char_to_index('c')] = 7;
    links[char_to_index('a')][char_to_index('d')] = 2;
    links[char_to_index('a')][char_to_index('f')] = 119;

    /* 'b' => array('d' => 4, 'e' => 6, 'f' => 8) */
    links[char_to_index('b')][char_to_index('d')] = 4;
    links[char_to_index('b')][char_to_index('e')] = 6;
    links[char_to_index('b')][char_to_index('f')] = 8;

    /* 'c' => array('d' => 5, 'e' => 3, 'f' => 2) */
    links[char_to_index('c')][char_to_index('d')] = 5;
    links[char_to_index('c')][char_to_index('e')] = 3;
    links[char_to_index('c')][char_to_index('f')] = 2;

    /* 'd' => array('e' => 7, 'f' => 4) */
    links[char_to_index('d')][char_to_index('e')] = 7;
    links[char_to_index('d')][char_to_index('f')] = 4;

    /* 'e' => array('f' => 3) */
    links[char_to_index('e')][char_to_index('f')] = 3;

    /* Инициализация структур путей */
    for (int i = 0; i < MAX_NODES; i++) {
        all_ways[i].count = 0;
    }

    char from_char = 'a';
    char to_char = 'f';
    int from = char_to_index(from_char);
    int to = char_to_index(to_char);

    /* Эмуляция: $ways = array($from => array($from => 0)); */
    WaysList *start_ways = &all_ways[from];
    strcpy(start_ways->entries[0].path, &from_char); /* Копируем символ 'a' */
    start_ways->entries[0].distance = 0;
    start_ways->count = 1;

    /* Основной цикл, аналог foreach ($links as $dot => $list) */
    /* Примечание: В оригинальном PHP коде перебор идет по всем узлам графа.
       Логика алгоритма в PHP немного специфична: он расширяет пути последовательно.
       Мы эмулируем эту логику, проходя по узлам в порядке их появления или просто по всем.
       Чтобы точно повторить логику "расширения", нам нужно пройти несколько итераций,
       так как в PHP цикл foreach по статическому массиву $links выполняется один раз,
       но внутри он обновляет $ways, который используется в текущей же итерации для следующих шагов?

       Стоп. Давайте внимательно посмотрим на PHP код:
       foreach ($links as $dot => $list) { ... }
       Внутри цикла мы читаем $ways[$dot]. Если $ways[$dot] еще не создан в предыдущих шагах цикла, он пропускается.
       Так как $links упорядочен как a, b, c, d, e, f, то:
       1. Обрабатываем 'a': у нас есть путь до 'a'. Обновляем пути до b, c, d, f.
       2. Обрабатываем 'b': у нас уже есть пути до 'b' (созданные на шаге 1). Обновляем пути до d, e, f.
       3. Обрабатываем 'c': у нас уже есть пути до 'c'. Обновляем d, e, f.
       ... и так далее.

       Это работает корректно только если порядок ключей в $links совпадает с топологическим порядком графа.
       В данном случае это так. Мы просто пройдемся циклом от 0 до 5.
    */

    for (int dot = 0; dot < MAX_NODES; dot++) {
        /* if (!isset($ways[$dot])) continue; */
        if (all_ways[dot].count == 0) {
            continue;
        }

        /* $curways = $ways[$dot]; */
        WaysList *cur_ways = &all_ways[dot];

        /* foreach ($list as $newdot => $dist) */
        for (int newdot = 0; newdot < MAX_NODES; newdot++) {
            int dist = links[dot][newdot];
            if (dist == 0) {
                continue; /* Нет соединения */
            }

            /* foreach ($curways as $way => $waydist) */
            for (int k = 0; k < cur_ways->count; k++) {
                WayEntry *current_entry = &cur_ways->entries[k];

                /* Вычисляем новый путь и расстояние */
                char new_path[MAX_PATH_LEN];
                strcpy(new_path, current_entry->path);
                new_path[strlen(new_path)] = index_to_char(newdot);
                new_path[strlen(new_path) + 1] = '\0'; /* На всякий случай, хотя strcpy уже поставил \0 после добавления символа? Нет, нужно аккуратно */

                /* Исправление конкатенации: */
                size_t len = strlen(new_path);
                new_path[len] = index_to_char(newdot);
                new_path[len + 1] = '\0';

                int new_dist = current_entry->distance + dist;

                /* Добавляем в список путей для newdot */
                WaysList *target_ways = &all_ways[newdot];
                if (target_ways->count < (MAX_NODES * MAX_NODES)) {
                    strcpy(target_ways->entries[target_ways->count].path, new_path);
                    target_ways->entries[target_ways->count].distance = new_dist;
                    target_ways->count++;
                }
            }
        }
    }

    /* Вывод результатов, аналог print_r($ways) */
    printf("Результаты (аналог print_r):\n");
    for (int i = 0; i < MAX_NODES; i++) {
        char node_name = index_to_char(i);
        if (all_ways[i].count > 0) {
            printf("Пути до узла '%c':\n", node_name);
            for (int j = 0; j < all_ways[i].count; j++) {
                printf("  Путь: %s, Расстояние: %d\n",
                       all_ways[i].entries[j].path,
                       all_ways[i].entries[j].distance);
            }
        } else {
            printf("Пути до узла '%c': не найдено\n", node_name);
        }
    }

    return 0;
}

#include <stdio.h>
#include <string.h>

/* Максимальное количество вершин в пути.
   Граф небольшой, 20 достаточно с запасом. */
#define MAX_PATH 26

/* Функция возвращает указатель на массив соседей для данной вершины.
   Вершины: 'a'..'f'. Возвращает NULL для неверной вершины. */
static const char *get_neighbors(char v) {
    switch (v) {
   case 'a': return "bcdz";
        case 'b': return "defz";
        case 'c': return "defz";
        case 'd': return "efz";
        case 'e': return "fz";
        case 'f': return "ghjz";
        case 'g': return "hijz";
        case 'h': return "ijkz";
        case 'i': return "jklz";
        case 'j': return "kmz";
        case 'k': return "lnoz";
        case 'l': return "mz";
        case 'm': return "noz";
        case 'n': return "oz";
        case 'o': return "pz";
        case 'p': return "qz";
        case 'q': return "rz";
        case 'r': return "sz";
        case 's': return "tuz";
        case 't': return "uvz";
        case 'u': return "vwz";
        case 'v': return "wz";
        case 'w': return "xyz";
        case 'x': return "yz";
        case 'y': return "z";
        case 'z': return "";
        default:  return NULL;
    }
}

/* Вспомогательная функция: найти индекс символа в строке.
   Возвращает -1, если не найден. */
static int str_index_of(const char *s, char c) {
    int i = 0;
    while (s[i] != '\0') {
        if (s[i] == c) return i;
        i++;
    }
    return -1;
}

int main(void) {
	int p =0;
    /* Первый путь (из PHP-скрипта) */
    char path[MAX_PATH];
    int path_len = 0;

    /* Инициализация первого пути: a -> b -> d -> e -> f */
    path[path_len++] = 'a';
    path[path_len++] = 'b';
    path[path_len++] = 'd';
    path[path_len++] = 'e';
    path[path_len++] = 'f';
    path[path_len++] = 'g';
    path[path_len++] = 'h';
    path[path_len++] = 'i';
    path[path_len++] = 'j';
    path[path_len++] = 'k';
    path[path_len++] = 'l';
    path[path_len++] = 'm';
    path[path_len++] = 'n';
    path[path_len++] = 'o';
    path[path_len++] = 'p';
    path[path_len++] = 'q';
    path[path_len++] = 'r';
    path[path_len++] = 's';
    path[path_len++] = 't';
    path[path_len++] = 'u';
    path[path_len++] = 'v';
    path[path_len++] = 'w';
    path[path_len++] = 'x';
    path[path_len++] = 'y';
    path[path_len++] = 'z';

    /* Вывод первого маршрута */
    {
        int i;
        for (i = 0; i < path_len; i++) {
            if (i > 0) printf(", ");
            printf("%c", path[i]);
        }
        printf("\n");
    }
p++;
    int j = path_len - 1;

    while (j > 0) {

        char current_v = path[j - 1];
        const char *neighbors = get_neighbors(current_v);

        /* В PHP: $ar = search_val($x, $j, $arr); */
        /* Здесь neighbors — это аналог $ar */

        int key = str_index_of(neighbors, path[j]);

        /* if (isset($ar[$key + 1])) */
        if ((key != -1) && (neighbors[key + 1] != '\0')) {
            /* $x = array_slice($x, 0, $j); */
            path_len = j;

            /* array_push($x, $ar[$key + 1]); */
            path[path_len++] = neighbors[key + 1];

            /* Достраиваем путь до 'f', всегда беря первого (нулевого) соседа */
            while (1) {

                char last_v = path[path_len - 1];
                if (last_v == 'z') {
                    break;
                }
                const char *next_neighbors = get_neighbors(last_v);
                /* В PHP: search_new_val_for_push_int_x(...)[0] */
                if (next_neighbors[0] != '\0') {
                    path[path_len++] = next_neighbors[0];
                } else {
                    /* Если нет соседей, а мы не в 'f', дальше идти некуда.
                       В логике PHP это не обрабатывается явно, но предотвратим зацикливание. */
                    break;
                }
            }

            j = path_len;

            /* print_r($x); */
            {
                int i;

                for (i = 0; i < path_len; i++) {
                    if (i > 0) printf(", ");
                    printf("%c", path[i]);
                }

                printf("\n");
				p++;


            }
        }

        j--;
    }
 printf("Количество путей: %d",p);
    return 0;
}

Количество путей: 22061
real	0m1,112s
user	0m0,300s
sys	0m0,377s

real	0m1,550s
user	0m0,409s
sys	0m0,415s

Количество путей: 22061
real	0m0,494s
user	0m0,108s
sys	0m0,255s

$ time php z.php > z.log
real	0m0,241s
user	0m0,076s
sys	0m0,156s

$ time php zz.php > z.log

real	0m0,074s
user	0m0,046s
sys	0m0,019s

 time php zz.php > z.log

real	0m0,041s
user	0m0,022s
sys	0m0,013s

Количество путей: 22061
real	0m0,013s
user	0m0,010s
sys	0m0,004s

real	0m3,731s
user	0m3,679s
sys	0m0,051s

type Node = char;
type Graph = BTreeMap<Node, Vec<Node>>;

// в реальном коде будет fn graph_parser(txt: &str) -> Result<Graph, Err> с анализом ошибок парсенья
fn graph_parser(txt: &str) -> Graph {
   txt.lines().filter(|s| !s.is_empty()).map(|s| {
           let ss: Vec<&str> = s.split('→').collect();
           let nodes: Vec<_> = ss[1].split(',')
               .map(|s| s.trim().chars().next().unwrap()).collect();
           (ss[0].trim().chars().next().unwrap(), nodes)
       }).collect()
}
// самое простое, но может продавить стек
fn number_paths_rec(graph: &Graph, beg: Node, end: Node, mut num: u64) -> u64 {
   if graph[&beg].is_empty() { return num }
   for &node in graph[&beg].iter() {
       if node == end {
           num += 1;
       } else {
           num = number_paths_rec(graph, node, end, num);
       }
   }
   num
}
// это не продавит но расчёт графа в 3-4 раза медленнее
fn number_paths_tail(graph: &Graph, beg: Node, end: Node) -> u64 {
   fn iter(graph: &Graph, end: Node, mut stack: Vec<Node>, mut num: u64) -> u64 {
       match stack.pop() {
           None => num,
           Some(curr_node) => {
               for &node in graph[&curr_node].iter() {
                   if node == end {
                       num += 1;
                   } else {
                       stack.push(node);
                   }
               }
               iter(graph, end, stack, num)
           }
       }
   }
   iter(graph, end, vec![beg], 0)
}

fn main() {
   let graph_txt = "
   a → b, c, d, z
   b → d, e, f, z
   c → d, e, f, z
   d → e, f, z
   e → f, z
   f → g, h, j, z
   g → h, i, j, z
   h → i, j, k, z
   i → j, k, l, z
   j → k, m, z
   k → l, n, o, z
   l → m, z
   m → n, o, z
   n → o, z
   o → p, z
   p → q, z
   q → r, z
   r → s, z
   s → t, u, z
   t → u, v, z
   u → v, w, z
   v → w, z
   w → x, y, z
   x → y, z
   y → z";
   let graph = graph_parser(graph_txt);
   let t0 = Instant::now();
   // let val = number_paths_rec(&graph, 'a', 'z', 0);
   let val = number_paths_tail(&graph, 'a', 'z');
   let t0 = t0.elapsed().as_micros() as f64;
   println!("{} us, {}", t0, val);
}

/*Поиск всех путей на графе. Переписан из кода PHP*/
#include <stdio.h>
#include <string.h>

static int array_search (const char *ar, char el) {
    int i = 0;
    while (ar[i] != '\0') {
        if (ar[i] == el) return i;
        i++;
    }
    return -1;
}

int main() {

int key;
char a[] = "bcdz";
char b[] = "defz";
char c[] = "defz";
char d[] = "efz";
char e[] = "fz";
char f[] = "ghjz";
char g[] = "hijz";
char h[] = "ijkz";
char i[] = "jklz";
char j[] = "kmz";
char k[] = "lnoz";
char l[] = "mz";
char m[] = "noz";
char n[] = "oz";
char o[] = "pz";
char p[] = "qz";
char q[] = "rz";
char r[] = "sz";
char s[] = "tuz";
char t[] = "uvz";
char u[] = "vwz";
char v[] = "wz";
char w[] = "xyz";
char x[] = "yz";
char y[] = "z";
char z[] = "";
char x2[26] = "abdefghijklmnopqrstuvwxyz";
char z2;

int  j2 = strlen(x2)-1;
int last_point = 'z';
int i2 = 0;
char *ar;
int x2_len = 0;
//Печать 1-го
for (i2=0; x2[i2] != '\0'; i2++)
printf("%c", x2[i2]);
printf("\n\r");
int ppp = 1;

while ( j2 != 0 )
 {

    if (x2[j2-1] =='a')
	ar = a;
	if (x2[j2-1] =='b')
	ar = b;
	if (x2[j2-1] =='c')
	ar = c;
	if (x2[j2-1] =='d')
	ar = d;
	if (x2[j2-1] =='e')
	ar = e;
	if (x2[j2-1] =='f')
	ar = f;
	if (x2[j2-1] =='g')
    ar = g;
if (x2[j2-1] =='h')
    ar = h;
if (x2[j2-1] =='i')
    ar = i;
if (x2[j2-1] =='j')
    ar = j;
if (x2[j2-1] =='k')
    ar = k;
if (x2[j2-1] =='l')
    ar = l;
if (x2[j2-1] =='m')
    ar = m;
if (x2[j2-1] =='n')
    ar = n;
if (x2[j2-1] =='o')
    ar = o;
if (x2[j2-1] =='p')
    ar = p;
if (x2[j2-1] =='q')
    ar = q;
if (x2[j2-1] =='r')
    ar = r;
if (x2[j2-1] =='s')
    ar = s;
if (x2[j2-1] =='t')
    ar = t;
if (x2[j2-1] =='u')
    ar = u;
if (x2[j2-1] =='v')
    ar = v;
if (x2[j2-1] =='w')
    ar = w;
if (x2[j2-1] =='x')
    ar = x;
if (x2[j2-1] =='y')
    ar = y;
if (x2[j2-1] =='z')
    ar = z;

  key =  array_search(ar, x2[ j2]);

       if ((key != -1) && (ar[key + 1] != '\0')) {
			//Ставим длину массива равной j
		 x2_len = j2;
		 //Заменим substr
		  x2[j2+1]='\0';

		  //Пишем в массив x
		   x2[x2_len++]= ar[key+1];


    if (x2[strlen(x2)-1] =='a')
	z2 = a[0];
		if (x2[strlen(x2)-1] =='b')
	z2 = b[0];
		if (x2[strlen(x2)-1] =='c')
	z2 = c[0];
	    if (x2[strlen(x2)-1] =='d')
	z2 = d[0];
		if (x2[strlen(x2)-1] =='e')
	z2 = e[0];
		if (x2[strlen(x2)-1] =='f')
	z2 = f[0];
	if (x2[strlen(x2)-1] =='g')
    z2 = g[0];
if (x2[strlen(x2)-1] =='h')
    z2 = h[0];
if (x2[strlen(x2)-1] =='i')
    z2 = i[0];
if (x2[strlen(x2)-1] =='j')
    z2 = j[0];
if (x2[strlen(x2)-1] =='k')
    z2 = k[0];
if (x2[strlen(x2)-1] =='l')
    z2 = l[0];
if (x2[strlen(x2)-1] =='m')
    z2 = m[0];
if (x2[strlen(x2)-1] =='n')
    z2 = n[0];
if (x2[strlen(x2)-1] =='o')
    z2 = o[0];
if (x2[strlen(x2)-1] =='p')
    z2 = p[0];
if (x2[strlen(x2)-1] =='q')
    z2 = q[0];
if (x2[strlen(x2)-1] =='r')
    z2 = r[0];
if (x2[strlen(x2)-1] =='s')
    z2 = s[0];
if (x2[strlen(x2)-1] =='t')
    z2 = t[0];
if (x2[strlen(x2)-1] =='u')
    z2 = u[0];
if (x2[strlen(x2)-1] =='v')
    z2 = v[0];
if (x2[strlen(x2)-1] =='w')
    z2 = w[0];
if (x2[strlen(x2)-1] =='x')
    z2 = x[0];
if (x2[strlen(x2)-1] =='y')
    z2 = y[0];
if (x2[strlen(x2)-1] =='z')
    z2 = z[0];


while(1) {
		//Если дошли до f выходим
		if ((x2[strlen(x2)-1] == last_point)) {
			//Пишем в x2
			 x2[x2_len++] = z2;
			 break;
		 }
			//Пишем в x2
			x2[x2_len++] = z2;
  if (x2[strlen(x2)-1] =='a')
	z2 = a[0];
		if (x2[strlen(x2)-1] =='b')
	z2 = b[0];
		if (x2[strlen(x2)-1] =='c')
	z2 = c[0];
	    if (x2[strlen(x2)-1] =='d')
	z2 = d[0];
		if (x2[strlen(x2)-1] =='e')
	z2 = e[0];
		if (x2[strlen(x2)-1] =='f')
	z2 = f[0];
	if (x2[strlen(x2)-1] =='g')
    z2 = g[0];
if (x2[strlen(x2)-1] =='h')
    z2 = h[0];
if (x2[strlen(x2)-1] =='i')
    z2 = i[0];
if (x2[strlen(x2)-1] =='j')
    z2 = j[0];
if (x2[strlen(x2)-1] =='k')
    z2 = k[0];
if (x2[strlen(x2)-1] =='l')
    z2 = l[0];
if (x2[strlen(x2)-1] =='m')
    z2 = m[0];
if (x2[strlen(x2)-1] =='n')
    z2 = n[0];
if (x2[strlen(x2)-1] =='o')
    z2 = o[0];
if (x2[strlen(x2)-1] =='p')
    z2 = p[0];
if (x2[strlen(x2)-1] =='q')
    z2 = q[0];
if (x2[strlen(x2)-1] =='r')
    z2 = r[0];
if (x2[strlen(x2)-1] =='s')
    z2 = s[0];
if (x2[strlen(x2)-1] =='t')
    z2 = t[0];
if (x2[strlen(x2)-1] =='u')
    z2 = u[0];
if (x2[strlen(x2)-1] =='v')
    z2 = v[0];
if (x2[strlen(x2)-1] =='w')
    z2 = w[0];
if (x2[strlen(x2)-1] =='x')
    z2 = x[0];
if (x2[strlen(x2)-1] =='y')
    z2 = y[0];
if (x2[strlen(x2)-1] =='z')
    z2 = z[0];

				}
				//Переменную ставим равной массиву
				 j2=strlen(x2);
				//Выводим
				printf("%s", x2);
				printf("\n\r");
				ppp++;
			}
 j2--;
		}
		printf("%d", ppp);
 }

real	0m0,544s
user	0m0,169s
sys	0m0,285s

real	0m0,097s
user	0m0,093s
sys	0m0,005s

 x2[j2+1]='\0';

/*Поиск всех путей на однонаправленном графе. Переписан из кода PHP на язык C стандарта 89*/
#include <stdio.h>
#include <string.h>
/*Объявим граф глобально*/
char a[] = "bcdz";
char b[] = "defz";
char c[] = "defz";
char d[] = "efz";
char e[] = "fz";
char f[] = "ghjz";
char g[] = "hijz";
char h[] = "ijkz";
char i[] = "jklz";
char j[] = "kmz";
char k[] = "lnoz";
char l[] = "mz";
char m[] = "noz";
char n[] = "oz";
char o[] = "pz";
char p[] = "qz";
char q[] = "rz";
char r[] = "sz";
char s[] = "tuz";
char t[] = "uvz";
char u[] = "vwz";
char v[] = "wz";
char w[] = "xyz";
char x[] = "yz";
char y[] = "z";
char z[] = "";
/*Вернёт элемент, который потом допишем в массив x*/
char element_search_to_push ( char *first_way) {

char elem_to_push;
  if (first_way[strlen(first_way)-1] =='a')
	elem_to_push = a[0];
		if (first_way[strlen(first_way)-1] =='b')
	elem_to_push = b[0];
		if (first_way[strlen(first_way)-1] =='c')
	elem_to_push = c[0];
	    if (first_way[strlen(first_way)-1] =='d')
	elem_to_push = d[0];
		if (first_way[strlen(first_way)-1] =='e')
	elem_to_push = e[0];
		if (first_way[strlen(first_way)-1] =='f')
	elem_to_push = f[0];
	if (first_way[strlen(first_way)-1] =='g')
    elem_to_push = g[0];
if (first_way[strlen(first_way)-1] =='h')
    elem_to_push = h[0];
if (first_way[strlen(first_way)-1] =='i')
    elem_to_push = i[0];
if (first_way[strlen(first_way)-1] =='j')
    elem_to_push = j[0];
if (first_way[strlen(first_way)-1] =='k')
    elem_to_push = k[0];
if (first_way[strlen(first_way)-1] =='l')
    elem_to_push = l[0];
if (first_way[strlen(first_way)-1] =='m')
    elem_to_push = m[0];
if (first_way[strlen(first_way)-1] =='n')
    elem_to_push = n[0];
if (first_way[strlen(first_way)-1] =='o')
    elem_to_push = o[0];
if (first_way[strlen(first_way)-1] =='p')
    elem_to_push = p[0];
if (first_way[strlen(first_way)-1] =='q')
    elem_to_push = q[0];
if (first_way[strlen(first_way)-1] =='r')
    elem_to_push = r[0];
if (first_way[strlen(first_way)-1] =='s')
    elem_to_push = s[0];
if (first_way[strlen(first_way)-1] =='t')
    elem_to_push = t[0];
if (first_way[strlen(first_way)-1] =='u')
    elem_to_push = u[0];
if (first_way[strlen(first_way)-1] =='v')
    elem_to_push = v[0];
if (first_way[strlen(first_way)-1] =='w')
    elem_to_push = w[0];
if (first_way[strlen(first_way)-1] =='x')
    elem_to_push = x[0];
if (first_way[strlen(first_way)-1] =='y')
    elem_to_push = y[0];
if (first_way[strlen(first_way)-1] =='z')
    elem_to_push = z[0];

	return elem_to_push;
}
/*Возвращает указатель на первый путь x*/
char *element_search ( char *first_way,  int j2 ) {

char *ar;
 if (first_way[j2-1] =='a')
	ar = a;
	if (first_way[j2-1] =='b')
	ar = b;
	if (first_way[j2-1] =='c')
	ar = c;
	if (first_way[j2-1] =='d')
	ar = d;
	if (first_way[j2-1] =='e')
	ar = e;
	if (first_way[j2-1] =='f')
	ar = f;
	if (first_way[j2-1] =='g')
    ar = g;
if (first_way[j2-1] =='h')
    ar = h;
if (first_way[j2-1] =='i')
    ar = i;
if (first_way[j2-1] =='j')
    ar = j;
if (first_way[j2-1] =='k')
    ar = k;
if (first_way[j2-1] =='l')
    ar = l;
if (first_way[j2-1] =='m')
    ar = m;
if (first_way[j2-1] =='n')
    ar = n;
if (first_way[j2-1] =='o')
    ar = o;
if (first_way[j2-1] =='p')
    ar = p;
if (first_way[j2-1] =='q')
    ar = q;
if (first_way[j2-1] =='r')
    ar = r;
if (first_way[j2-1] =='s')
    ar = s;
if (first_way[j2-1] =='t')
    ar = t;
if (first_way[j2-1] =='u')
    ar = u;
if (first_way[j2-1] =='v')
    ar = v;
if (first_way[j2-1] =='w')
    ar = w;
if (first_way[j2-1] =='x')
    ar = x;
if (first_way[j2-1] =='y')
    ar = y;
if (first_way[j2-1] =='z')
    ar = z;
	return ar;
}

static int array_search (const char *ar, char el) {
    int i = 0;
    while (ar[i] != '\0') {
        if (ar[i] == el) return i;
        i++;
    }
    return -1;
}

int main(void) {
int key;
/*Первый путь*/
char first_way[26] = "abdefghijklmnopqrstuvwxyz";
char elem_to_push;

int  j2 = strlen(first_way)-1;
int last_point = 'z';
int i2 = 0;
char *ar;
int first_way_len = 0;

/*Печать 1-го*/
for (i2=0; first_way[i2] != '\0'; i2++)
printf("%c", first_way[i2]);
printf("\n\r");
int all_ways_count = 1;


while ( j2 != 0 )
 {
    /*Поиск элемента*/
	ar=element_search (first_way,  j2 );
	/*Поиск ключа*/
   key =  array_search(ar, first_way[ j2]);
       if ((key != -1) && (ar[key + 1] != '\0')) {
			/*Ставим длину массива равной j2*/
		 first_way_len = j2;
		 /*Заменим substr*/
		  first_way[j2+1]='\0';
		  /*Пишем в массив x*/
		   first_way[first_way_len++]= ar[key+1];
			elem_to_push=element_search_to_push(first_way);
while(1) {
		/*Если дошли до f выходим*/
		if ((first_way[strlen(first_way)-1] == last_point)) {
			/*Пишем в first_way*/
			 first_way[first_way_len++] = elem_to_push;
			 break;
		 }
			/*Пишем в first_way*/
			first_way[first_way_len++] = elem_to_push;
		elem_to_push=element_search_to_push(first_way);
				}
				/*Переменную ставим равной массиву*/
				 j2=strlen(first_way);
				/*Выводим*/
				printf("%s", first_way);
				printf("\n\r");
				all_ways_count++;
			}
 j2--;
		}
		printf("%d", all_ways_count);
 }

Evaluation took:
  0.062 seconds of real time
  0.062159 seconds of total run time (0.048126 user, 0.014033 system)