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

но, видимо, программно

Та так пишешь как будто тебе в школе дали такое задание и ты тут советуешься как его решать.

Считается без всяких программ на бумажке минут за 10 или меньше. Ответ верный да.

Видишь строчку «a -> b,c,d,z» - ставишь справа от строк b,c,d,z единицы.

Затем видишь строчку «b -> d,e,f,z 1» - прибавляешь эту единицу что справа к d,e,f,z (у d получается уже 2 т.к. ему единицу ещё раньше приписали).

Затем то же самое «c -> d,e,f,z 1».

Затем строка «d -> e,f,z 3» - прибавляешь тройку к e,f,z.

Итд.

В яндекс собесишься?

Да, какая школа в моем возрасте?! Интересно, кто как решает такое.

Ты хочешь сказать, что можно посчитать по какой-то формуле?! Не думал об этом. Строго вручную уж очень утомительно считать.

Пора тебе всем Лором скинуться на второй Макбук Про.

Этого ещё не хватало…

Ты хочешь сказать, что можно посчитать по какой-то формуле?!

Белов В. В., Воробьев Е. М., Шаталов В. Е. - Теория графов. — М.: Высш. школа, 1976.

Надо понимать, что всё уже придумано до нас.

утомительно считать

Уроки в школе длятся по 40-60 минут, и как-то никого кроме двоечников не утомляют. А тут всего 10 минут, и вся арифметика уже в 3 классе должна быть полностью понятна (а без понимания и в 1 классе можно выполнить).

ААаа… там вроде сумма размещений с вычитанием того, чего нет?!

Строго вручную уж очень утомительно считать.

Сервис с картинками, алгоритмами и обучающим видео для лентяев Graph Online © (graphonline.ru).

Аааа…. Т.е. ты таки хочешь сказать, что такие графы считаются простым сложением?! Я взял маленький граф и вроде получилось:

$a = array('b', 'c', 'd', 'e');
$b = array('c', 'd', 'e');
$c = array('d', 'e');
$d = array('e');
$е = array();

Методика: 4+3+1 Ответ: 8

Нет, возведением в степень.

2 в третьей степени = 8.

Да. Действительно меньше 10 минут ушло простой арифметикой:

a → b, c, d, z		22061
b → d, e, f, z		8824
c → d, e, f, z		8824
d → e, f, z	        4412
e → f, z		2206
f → g, h, j, z		2205
g → h, i, j, z		1297
h → i, j, k, z		713
i → j, k, l, z		389
j → k, m, z		194
k → l, n, o, z		129
l → m, z		65
m → n, o, z		64
n → o, z		32
o → p, z		31
p → q, z		30
q → r, z		29
r → s, z		28
s → t, u, z 		27
t → u, v, z 		16
u → v, w, z 		10	
v → w, z    		5
w → x, y, z 		4 
x → y, z 		2 
y → z 			1
z → (нет исходящих) 0

P.S. Через матрицу смежности, как я понял, предлагается использовать степени. (Но там не очень ясно. Сети пишут, что на таких графах - степени - формальны). (Бегло если глянуть, то растет функция, и правда, как что-то близкое к степени двойки).

пути не искал, но одобряю подобные темы на ЛОР

Вот последний вариант кода.

1. Находит количество всех путей.
2. Выводит все пути.
3. Показывает минимальный от a до z с расстоянием.
4. Показывает все минимальные пути меньше заданного. Допустим, все пути из a в z меньше 10.

По замыслу должен работать для любых n на ориентированных упорядоченных графах подобного рода:

<?php

function search_new_val_for_push_int_x($x, $j, $arr) {
    foreach($arr as $key => $val) {
        if($x[count($x) - 1] == $key)
            return $arr[$key];
    }
}

function search_val($x, $j, $arr) {
    foreach($arr as $key => $val) {
        if($x[$j - 1] == $key)
            return $arr[$key];
    }
}

//Граф
$a = array('b', 'c', 'd', 'z');
$b = array('d', 'e', 'f', 'z');
$c = array('d', 'e', 'f', 'z');
$d = array('e', 'f', 'z');
$e = array('f', 'z');
$f = array('g', 'h', 'j', 'z'); // дополнено
$g = array('h', 'i', 'j', 'z'); // дополнено
$h = array('i', 'j', 'k', 'z'); // дополнено
$i = array('j', 'k', 'l',  'z'); // дополнено
$j = array('k', 'm', 'z'); // дополнено
$k = array('l', 'n', 'o',  'z'); // дополнено
$l = array('m',  'z'); // дополнено
$m = array('n', 'o', 'z'); // дополнено
$n = array('o',  'z'); // дополнено
$o = array('p',  'z'); // дополнено
$p = array('q',  'z'); // дополнено
$q = array('r',  'z'); // дополнено
$r = array('s',  'z'); // дополнено
$s = array('t', 'u',  'z'); // дополнено
$t = array('u', 'v', 'z'); // дополнено
$u = array('v', 'w',  'z'); // дополнено
$v = array('w', 'z'); // дополнено
$w = array('x', 'y', 'z'); // дополнено
$x = array('y', 'z'); // дополнено
$y = array('z'); // дополнено
$z = array(); // конечная точка

// Ребра с расстояниями
$distance = array(
    'ab' => '3', 'ac' => '7', 'ad' => '2', 'az' => '119',
    // B
    'bd' => '4', 'be' => '6', 'bf' => '1', 'bz' => '8',
    // C
    'cd' => '5', 'ce' => '3', 'cf' => '9', 'cz' => '2',
    // D
    'de' => '7', 'df' => '4', 'dz' => '6',
    // E
    'ef' => '3', 'ez' => '8',
    // F
    'fg' => '2', 'fh' => '9', 'fj' => '5', 'fz' => '3',
    // G
    'gh' => '7', 'gi' => '4', 'gj' => '6', 'gz' => '2',
    // H
    'hi' => '9', 'hj' => '3', 'hk' => '8', 'hz' => '5',
    // I
    'ij' => '2', 'ik' => '7', 'il' => '4', 'iz' => '9',
    // J
    'jk' => '6', 'jm' => '3', 'jz' => '8',
    // K
    'kl' => '5', 'kn' => '9', 'ko' => '2', 'kz' => '7',
    // L
    'lm' => '4', 'lz' => '6',
    // M
    'mn' => '8', 'mo' => '3', 'mz' => '9',
    // N
    'no' => '5', 'nz' => '2',
    // O
    'op' => '7', 'oz' => '4',
    // P
    'pq' => '9', 'pz' => '6',
    // Q
    'qr' => '3', 'qz' => '8',
    // R
    'rs' => '5', 'rz' => '2',
    // S
    'st' => '7', 'su' => '4', 'sz' => '9',
    // T
    'tu' => '3', 'tv' => '8', 'tz' => '5',
    // U
    'uv' => '6', 'uw' => '2', 'uz' => '9',
    // V
    'vw' => '4', 'vz' => '7',
    // W
    'wx' => '8', 'wy' => 3, 'wz' => '6',
    // X
    'xy' => '9', 'xz' => '2',
    // Y
    'yz' => '5'
);
//Доп. массив
$arr = array(
    'a' => $a,
    'b' => $b,
    'c' => $c,
    'd' => $d,
    'e' => $e,
    'f' => $f,
    'g' => $g,
    'h' => $h,
    'i' => $i,
    'j' => $j,
    'k' => $k,
    'l' => $l,
    'm' => $m,
    'n' => $n,
    'o' => $o,
    'p' => $p,
    'q' => $q,
    'r' => $r,
    's' => $s,
    't' => $t,
    'u' => $u,
    'v' => $v,
    'w' => $w,
    'x' => $x,
    'y' => $y,
    'z' => $z
);

$arr2 = array($a, $b, $c, $d, $e, $f,
    $g, $h, $i, $j, $k, $l,
    $m, $n, $o, $p, $q, $r,
    $s, $t, $u, $v, $w, $x,
    $y, $z
);
// Массив для нахождения первого пути
$arr3 = array(
    'a', 'b', 'c', 'd', 'e', 'f',
    'g', 'h', 'i', 'j', 'k', 'l',
    'm', 'n', 'o', 'p', 'q', 'r',
    's', 't', 'u', 'v', 'w', 'x',
    'y', 'z'
);


// Первый путь находим в первом столбце матрицы по 0 индексам, от a до f
$first_way[] = 'a';
// Пункт назначения
$last_point = 'z';
$x = $arr2[0];
$z = $x[0];

// Найдем остальные
for($i = 0; $i < count($arr3); $i++) {
    if(isset($x[0])) {
        $z = $x[0];
        $first_way[] = $z[0];
    }
    if(isset($arr3[$i])) {
        for($i; $arr3[$i] != $z; $i++);
        $x = $arr2[$i];
    }
}

$all_ways3[] = $first_way;
/*
// Первая точка
$first_point = array('a');
$last_point = 'm';
$add_new_point = $first_point[0];
$first_way[] = $first_point[0];
$i=0;
// Поиск первого маршрута
while(1) {
    if(!isset(${$add_new_point}[0]))
        break;
    $add_new_point = ${$add_new_point}[0];
    $first_way[] = $add_new_point;
    if ($first_way[$i] == $last_point || $i >=  count($first_way)) {
        break;
    }
    $i++;
}
*/
// Печатаем первый маршрут
print_r($first_way);
print "<br/>";
// Минимальный путь, пока произвольное число
$min_way_dist = 10;
$min_distances = 1000;
$x = $first_way;
$j = count($x) - 1;
$count_ways = 1;

while($j != 0) {
    // Ищем новое значение. Значение будет использовано в качестве имени массива.
    $ar = search_val($x, $j, $arr);
    $key = array_search($x[$j], $ar);
    //if (${$x[$j-1]}[$key+1] != '') {
    if (isset($ar[$key + 1])) {
        $x = array_slice($x, 0, $j);
        array_push($x, $ar[$key + 1]);
        //$z=$x[count($x)-1];
        // найдем все 0-ые индексы
        if (isset(search_new_val_for_push_int_x($x, $j, $arr)[0]))
            $z = search_new_val_for_push_int_x($x, $j, $arr)[0];

        while (1) {
            if ($x[count($x) - 1] == $last_point) {
                if (isset(search_new_val_for_push_int_x($x, $j, $arr)[0]))
                    array_push($x, $z);
                break;
            }
            if (isset(search_new_val_for_push_int_x($x, $j, $arr)[0])) {
                array_push($x, $z);
                if (isset(search_new_val_for_push_int_x($x, $j, $arr)[0]))
                    $z = search_new_val_for_push_int_x($x, $j, $arr)[0];
            }
        }

        $j = count($x);
        $all_ways3[0] = $x;
        print_r($x);
        ///////////////////////////////////// Блок 2 ////////////////////////////////////////////////
        // Найдём минимальный расстояние и путь


              $sum =   $min_distances = $sum;



        foreach($all_ways3 as $key => $val) {
            $sum = 0;
            foreach ($val as $k => $way) {
                if (isset($val[$k+1]) && isset($val[$k])) {
                    if ($val[$k] == $last_point)
                        break;
                    $rib = $val[$k] . $val[$k+1];
                    foreach($distance as $r => $v) {
                        if ($r == $rib) {
                            $sum += $v;
                        }
                    }
                }
            }

        }
                  if ($sum < $min_distances) {
          $min_distances = $sum;
           $min_way_name = $all_ways3 ;
           if ( $min_distances  < $min_way_dist ) {
			   $all_shorts_ways[] =$all_ways3;
			    $all_shorts_ways_dist[] = $min_distances;
		   }
	  }

        //////////////////////////////////////////////// Конец блока 2 ////////////////////////////////////////
        ///////////////////////////////////////////////////////////////////////////////////////////////////////////
        /* Тут считаем все пути */
        $count_ways++;
        print "<br/>";
    }
    $j--;
}

/////////////////// Итоги ////////////////////////////////////////////////////////////

print ' Все короткие пути меньше 10 ';
 print_r(  $all_shorts_ways);
 print ' Расстояния ';
  print_r($all_shorts_ways_dist);
  print ' Количество всех путей ';
print $count_ways;
print ' Минимальное расстояние: ';
print_r($min_distances);
print ' Путь:  ';
print_r($min_way_name);
?>

Да, какая школа в моем возрасте?! Интересно, кто как решает такое.

А откуда ты берешь такие задачки?

Именно эту из головы. Вернее, из жизни. Следствие того, что некоторое время работал курьером.

P.S. Не хочу навязывать мнение, но многие в общем глубоко, казалось бы, теоретические вещи взяты из практических запросов.
Пример: знаменитая задача о письмах и т.д.

И как можно применить на практике посчитанное число возможных путей?

Конкретно именно эту задачу?! Тут, конечно, поле для творчества.

Если обходишь дома или подъезды или и то, и другое, в одном или даже нескольких районах (или объезжаешь), при этом у тебя есть какая-то точка (она же финальная), то можешь посчитать короткий путь к ней или несколько вариантов путей. Это, очень, «натуралистичный» пример. Если у тебя более 20 точек, то может иметь смысл.

Дальше предположения. В общем может быть полезно и интересно для тех, кто занимается логистикой, транспортом и т.д.

Может быть, применимо где-то в построении разных сетей.

Может быть применима в шахматах и т.д.

P.S. Может быть даже применима для обхода большого супермаркета с тележкой :)

Дальше фантастика: для поиска ближайшего пути к какой-нибудь галактике или звезде :)

Или поиск кратайшего пути до туалета на даче.

Или расчёта прохода по грибным местам в лесу.

то можешь посчитать короткий путь к ней или несколько вариантов путей

Ну это понятно, это конечно нужно, вопрос был про то, зачем считать количество вариантов путей)

Ужас какой...

<?php
  $links = array(
    'a' => array('b'=>3, 'c'=>7, 'd'=>2, 'z'=>119),
    'b' => array('d'=>4, 'e'=>6, 'f'=>1, 'z'=>8),
    'c' => array('d'=>5, 'e'=>3, 'f'=>9, 'z'=>2),
    'd' => array('e'=>7, 'f'=>4, 'z'=>6),
    'e' => array('f'=>3, 'z'=>8),
    'f' => array('g'=>2, 'h'=>9, 'j'=>5, 'z'=>3),
    'g' => array('h'=>7, 'i'=>4, 'j'=>6, 'z'=>2),
    'h' => array('i'=>9, 'j'=>3, 'k'=>8, 'z'=>5),
    'i' => array('j'=>2, 'k'=>7, 'l'=>4,  'z'=>9),
    'j' => array('k'=>6, 'm'=>3, 'z'=>8),
    'k' => array('l'=>5, 'n'=>9, 'o'=>2,  'z'=>7),
    'l' => array('m'=>4,  'z'=>6),
    'm' => array('n'=>8, 'o'=>3, 'z'=>9),
    'n' => array('o'=>5,  'z'=>2),
    'o' => array('p'=>7,  'z'=>4),
    'p' => array('q'=>9,  'z'=>6),
    'q' => array('r'=>3,  'z'=>8),
    'r' => array('s'=>5,  'z'=>2),
    's' => array('t'=>7, 'u'=>4,  'z'=>9),
    't' => array('u'=>3, 'v'=>8, 'z'=>5),
    'u' => array('v'=>6, 'w'=>2,  'z'=>9),
    'v' => array('w'=>4, 'z'=>7),
    'w' => array('x'=>8, 'y'=>3, 'z'=>6),
    'x' => array('y'=>9, 'z'=>2),
    'y' => array('z'=>5),
    'z' => array()
  );
  $from = 'a';
  $to = 'z';
  // предполагаем что в массиве выше все переходы только вперёд по списку
  // если нет, то его надо ещё отсортировать чтобы это стало так

  /* если надо посчитать только количество путей то ВЕСЬ код - 8 строк ниже */
  $dots = array();
  foreach($links as $dot => $xxx) $dots[$dot] = 0;
  $dots[$from] = 1;
  foreach($links as $dot => $list) {
    $value = $dots[$dot];
    foreach($list as $newdot => $dist) $dots[$newdot] += $value;
  }
  echo "всего путей: ".$dots[$to]."\n";

  /* если нужен список путей */
  $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;
      }
    }
  }
  $ways = $ways[$to]; // нужны только пути до 'z'
  asort($ways);
  echo "всего путей: ".count($ways)."\n";
  echo "список путей по возрастанию длины:\n";
  foreach($ways as $way => $dist) echo "  $way  = $dist\n";

Почти половина из примерно получаса времени ушла на переделывание твоего наркоманского формата входных данных в нормальный. И нафиг ты числа в кавычки засунул?

Твои пункты 2-4 сводятся к выводу списка путей, отсортированного по длине, зачем ты на ровном месте целых 3 пунтка про это выдумал?

Я надеюсь свой код ты всё-таки писал сам, без участия бредогенераторов, а этот код соответственно посмотришь и подумаешь почему у тебя вместо такого же получилась простыня в 5+ раз длиннее и как в следующий раз такого избежать.

Только попросил массив ребер достроить до z.

Мне кажется, очевидно, что такой код сеть сгенерировать не сможет.

Почему наркоманского?! Мне на лету пришла такая идея, я увидел, что она сработает и реализовал. У меня не прям так много времени, чтобы много тюнингом заниматься.

Но спасибо, да :)

Я когда сосредоточен на алгоритме, уже реализованное не трогаю.

В общем, что-то близкое к методу итеративной разработки, сначала делаешь так, потом улучшаешь или кто-то улучшает. Но пример, скорее всего, дальше репозитария не пойдет, поэтому и доделывать его особого смысла нет.

И этот код последовательно переделывался из этого: https://habr.com/ru/articles/340646/

В 2017 бредогенераторы ещё не были распространены.

И первый код вглядел так:

<?php

error_reporting(E_ALL);
$a=array('b','c','d');
$b=array('d','e','f');
$c=array('d','e','f');
$d=array('e');
$e=array('f');
$f=array();
$x=array('a','b','d','e','f');
print_r ( $x );
print "\n";
$j=count($x)-1;
while($j !=0) {
	$key = array_search($x[$j], ${$x[$j-1]});
if (${$x[$j-1]}[$key+1] != '') {
	$x=array_slice($x, 0, $j);
	array_push($x, ${$x[$j-1]}[$key+1]);
	$z=$x[count($x)-1];
	$z=${$z}[0];
while (1) {
	if ($x[count($x)-1]=='f') {	array_push($x, $z);  break ;}
	array_push($x, $z);
	$z=${$z}[0];
	}
	$j=count($x);
	print_r ( $x );
	echo "\n";
		}
$j--;
}
?>

Почему наркоманского?!

Потому что вместо логичного массива «откуда, куда, длина», занимающего 26 коротких строк для данных, у меня там 5 сущностей на больше 100 строк, из которых только первая выглядит хорошо (но зачем-то раскидана по отдельным переменным), вторая неудобная, третья - костыль в превращению первой наконец в нормальный массив, а зачем нужны четвёртая и пятая мне уже лень даже разбираться.

уже реализованное не трогаю.

Это общеизвестный подход, и то, что из него получается, называется «лапша» (или спагетти-код у иностранцев), можешь поискать по этим словами негативные стороны данного явления.

Хорошо, но мне был важен в конечном счете результат. Увидеть, что идея работает на практике. Мне важен сам факт - свершившееся событие: ого! Моя идея работает.

Ещё боюсь, что если сильно зациклится на структуре и всяких красотах, то пропадет алгоритмическое чутье. :)

Ну, а если кому-то нужно для практических целей, то есть профи… и т.д.

Потому что в реальности кратчайший необязательно удобный.

Кстати, сейчас ехал на метро и подумал, что варианты, как проехать на метро из точки а в точку z - хороший пример.

Простыня ещё 5 раз больше, потому что сам алгоритм «неклассический», с 0 написан. Совпадения случайны.

Т.е. не Декстра, dfs, bfs, pfs, mfs и даже не gps и не пфр

Идёшь в лес за грибами, а грибы идут за тобой. Они свой лес знают всяко лучше, чем ты. Если настигнет мухомор, то отправишься прямиком в космос. Хотя видно его из далека, есть шанс убежать. Главное не выбегать из лесу на пшеничное поле...

Можно не по грибы. Кратчайший путь имеет смысл искать, если ходить можно только по тропинкам.

Но в общем для обычной ситуации мало применим. Так как инстинкт работает лучше …

Конечно по формуле. Теория графов, все дела. Алгоритмы подсчёта путей. Правда смотри, в общем случае это даже не NP полная задача, а #P полная задача.

Какое-то малоосмысленное оправдание.

Ты думаешь что мой код, где алгоритм (не считая скобок и вывода результата в echo) занимает 7 строк, написан не с нуля?

В логистике, например у воюющих армий. Надо везти в прифронтовой город N-ск боеприпасы, солдат, еду и топливо из города в тылу, где это производится. Следует установить, сколькими путями может поехать груз, чтоб диверсанты могли его обнаружить и уничтожить или подсчитать сколько привезут. Ну там ИРЛ ещё сложнее задача, т.к. диверсантов ограниченное число и потому их надо размещать в тех местах, где груз точно поедет, но в то же время, чтоб не было слишком палевно, потому как в узких местах точно будут трясти всех подряд.

Ну, а если кому-то нужно для практических целей, то есть

Как решать транспортные задачи линейного программирования © (semestr.ru).

А зачем мне оправдываться.

Я делаю на языке модель.

Меня в редких случаях волнует тюнинг кода.

Я убедился в том, что идея работает…

Да и хорошим кодом можно избаловать пользователя или даже себя. Код и должен быть немного запутан… Чтобы не было слишком легко… Но не во всех случаях, конечно…

Это не «тюнинг кода». У тебя вместо полностью достаточного кода, занимающего несколько строк, огромная простыня с целой пачкой лишних, полностью бесполезных сущностей (бесполезных - потому что всё работает без них), которые даже читать не хочется, не говоря уж о поиске в них потенциальных ошибок. Ну и работает он скорее всего дольше.

Это примерно из той же серии, как умножение двух чисел вместо записи a*b реализовывать через создание «объектов» чисел, затем разбор из на отдельные объекты «цифра», которые будут отдельным алгоритмом на целую страницу умножаться в столбик, а затем назад конвертироваться в число. Итог - куча впустую потраченного времени, и не более того. И твоего, и тех кто потом будет пытаться изучать данный алгоритм.

Код и должен быть немного запутан…

Нет, не должен.

А как ты видишь проход по всем элементам массива в данном случае?! Через ООП?! Но это будет все равно мало понятный код.

Да. У меня воткнуто много вложенных циклов. Да. В тот момент, когда я писал, мне было удобно работать с данными именно так. Моим кодом все равно пользоваться никто не будет.

Если однажды мне придет в голову уже что-то конкретное, для чего можно использовать этот алгоритм, то, м.б., я перепишу его.

А как ты видишь проход по всем элементам массива в данном случае?!

Я тебе код выше прислал как это надо было сделать! Ты его читал? Сам алгоритм там всего 7 строк и ещё 3 строки закрывающих скобок. Как можно запутаться в 7 строчках кода?

Вложенных циклов там требуется всего три, проход по элементам массива в пхп делается командой foreach - и она занимает всего одну строку.

И для «поиска значения в массиве по ключу» не нужны никакие циклы, которые там у тебя везде накручены, этот «поиск» делается одним оператором «квадратные скобки», то есть $arr[6] это «поиск» элемента 6 в массиве $arr.

Проверил твой код. Отлично работает.

Но, что не нравится лично мне:

1. явный массив массивов.

Кстати, в оригинальном коде, с переменными переменных, циклов всего два, если не считать всякие array_search

Ну да ладно. Отлично, если есть вариант лучше моего…

явный массив массивов

Это называется хорошее структурирование данных. Именно такой массив позволяет нативными для php средствами перебирать как исходные точки, так и рёбра, идущие от нужной точки, сразу видеть их длину и всё это в 1-2 простые строчки кода.

Не надо переизобретать огромные алгоритмы для того, что уже есть в языке. Переизобретением алгоритмов кстати страдают всякие фреймворко-писатели, за что их тоже следует осуждать. В итоге код для этих фреймворков начинает занимать вместо 500 байт какие-нить 100 кбайт.

Кстати, в оригинальном коде, с переменными переменных, циклов всего два,

У тебя там горы всяких array_slice, array_push итд, вместо простого оператора квадратных скобок.

Ну да ладно. Отлично, если есть вариант лучше моего…

Я не «вариант» присылал а пример для того чтобы ты его посмотрел и исправил подход написания 50-кратно удлинённого на ровном месте кода.

$ways = array($from => array($from => 0));

Вот эта конструкция пока не очень понятна. Через нее получаем доступ к 0 индексам вложенных массивов, чтобы собрать путь?! Весь механизм пока не очень ясен.

Это означает создать массив, у которого есть единственный индекс $from, по этому индексу хранится вложенный массив, у которого тоже единственный индекс $from, по которому хранится расстояние пути от $from до $from, которое очевидно равно нулю. А затем, перебирая по очереди все рёбра двумерным циклом, к этому пустому пути добавляются все возможные следующие звенья.

Первый (внешний) индекс массива - это то, куда мы можем попасть (в самом начале, пока мы не смотрели рёбра, попасть мы можем только в стартовую точку $from). Индекс вложенного массива (второй) - это путь, которым мы в указанное место попадём из стартовой точки (он тут тоже состоит только из названия этой точки т.к. никуда идти не надо). Затем мы допустим видим что из точки 'a' можно дойти до точки 'b' за расстояние 3, и создаём у первого массива индекс 'b' (будет туда записывать список путей до 'b'), и в него записываем длину уже пройденного пути ('a' -> 'a' = 0) плюс длину добавки ('a' -> 'b' = 3) для пути 'ab'.

Мне кажется, что у тех, кто берется объяснять алгоритмы есть какая-то общая проблема.

«Затем мы допустим видим что из точки ‘a’ можно дойти до точки ‘b’ за расстояние 3, и создаём у первого массива индекс ’b».

Перечитай объяснение где-нибудь через неделю. Как бы со стороны, будто не ты его писал…

Работа кода по шагам, если следовать описанию, не просматривается. Какая переменная хранит путь?! В какой момент в нее добавляется b? В какой момент d?! Каково условие добавление?!

У тебя весь результат оказался в одном массиве. Что, как бы сказать, не очень гуд.

Никакая переменная путь не хранит. Никакой отдельный путь хранить не нужно, зачем? Есть массив известных путей, он один единственный и его ни с чем не перепутать. В нём хранятся все известные пути сразу.

$ways['f'] = список путей к точке f.

И вот этот самый $ways в цикле дополняется новыми обнаруженными путями по ходу сканирования списка рёбер.

Вот мы знаем путь abef, например, его длина 12. Он записан так: $ways['f']['abef'] = 12.

Смотрим список рёбер, идущих от f: 'f' => array('g'=>2, 'h'=>9, 'j'=>5, 'z'=>3), и вот, был abef=12 а теперь есть ещё abefg = 12+2, abefh = 12+9, abefj = 12+5, abefz = 12+3 (откуда это взялось надеюсь не надо объяснять). Эти пути мы нигде по-отдельности не храним (зачем?), а сразу записываем в тот же массив $ways:

$ways['g']['abefg'] = 14;
$ways['h']['abefh'] = 21;
$ways['j']['abefj'] = 17;
$ways['z']['abefz'] = 15;

Путь бы вывести 1 раз после его нахождения. Т.е. если возможно,обнулить массив для следующего пути. От накопления массива, на мой взгляд, лучше избавиться.

Как я понял:

1. Первый цикл обходит links. Второй обходит вложенный.

2. Т.е. второй цикл, первая итерация (нулевая) - обход a=>array. На нулевой итерации $ways[$dot] ещё не установлен.

3. На первой итерации (1) $curways равен array a. Далее обход curways. Формируется новый массив массивов ways, у которого внутренний индекс (каждого) собран конкатенацией его внешненего индекса и внутренних индексов. (с расстояниями понятно). Третий цикл в начале обходит первый же массив и индекс way равен а. Долго клеешь каждый путь.

Я что-то не заметил сразу, что конкатенация в ways изменяет и сам ключ в массиве, добавляя элемент. Хотя логично, если дальше есть присвоение нового значения для рассмотрения.

Т.е. каждый раз обходишь curways И удлинняешь индекс конкатенацией, добавляя значение в этом массив заново?!

Очень рекурсивный подход напоминает.

$curways это просто сокращённое написание для $ways[$dot], чтобы код проще читался.

Да, на каждой точке обходятся все способы попасть в эту точку ($ways[$dot]), к каждому из них конкатенируются способы пойти из этой точки дальше (рёбра) и полученный список удлинённых на один ход путей рассовывается по $ways[следующие_точки][новые_пути].

Если тебя беспокоит расход памяти на уже ненужные старые пути, можно делать unset($ways[$dot]); после проверки всх рёбер, начинающихся из $dot.

Зашёл сказать, что вы все наркоманы. Задача решается элементарно (php не знаю, поэтому scheme), если выбрать правильное представление данных. Надо перейти от массива записей откуда → куда к словарю куда ← откуда. Тогда, например, поиск числа путей в «z» из «a» решается элементарным рекурсивным обходом и дополнительным словарём узел ← количество путей в этот узел из «a». Собственно в коде выше большая часть для изменения представления данных, а само решение

(define (count-paths to)
  (or
   (hash-ref counter to)
   (hash-set! counter to
          (fold
           (λ (to acc)
         (+ acc (count-paths to)))
           0
           (hash-ref graph to)))))

Количество путей для узла либо уже известно, либо равняется сумме колечеств для узлов, ведущих в данный. (если в d ведут пути из b и с, в с из b и a, а в b из a, то для b мы имеем 1, для c — 2, а для d — 1 + 2 = 3).