У меня есть этот массив:
Array
(
[V] => Array
(
[0] => S
)
[L] => Array
(
[0] => M
[1] => Z
[2] => G
)
[S] => Array
(
[0] => T
[1] => X
[2] => K
)
[T] => Array
(
[0] => D
)
[B] => Array
(
[0] => E
[1] => N
[2] => Y
)
[W] => Array
(
[0] => J
[1] => Y
)
[G] => Array
(
[0] => A
[1] => K
)
[J] => Array
(
[0] => T
)
[X] => Array
(
[0] => H
)
[E] => Array
(
[0] => Z
)
[N] => Array
(
[0] => B
)
[Z] => Array
(
[0] => A
[1] => M
)
[U] => Array
(
[0] => R
)
[F] => Array
(
[0] => C
[1] => V
)
[I] => Array
(
[0] => F
)
[C] => Array
(
[0] => O
[1] => P
[2] => T
)
[Q] => Array
(
[0] => L
[1] => V
)
[Y] => Array
(
[0] => C
)
[K] => Array
(
[0] => T
[1] => P
[2] => A
)
[A] => Array
(
[0] => J
)
[M] => Array
(
[0] => W
)
[R] => Array
(
[0] => I
)
[P] => Array
(
[0] => K
[1] => N
)
[O] => Array
(
[0] => G
)
[H] => Array
(
[0] => Q
)
[D] => Array
(
[0] => U
)
)
Serialized:
a:26:{s:1:"V";a:1:{i:0;s:1:"S";}s:1:"L";a:3:{i:0;s:1:"M";i:1;s:1:"Z";i:2;s:1:"G";}s:1:"S";a:3:{i:0;s:1:"T";i:1;s:1:"X";i:2;s:1:"K";}s:1:"T";a:1:{i:0;s:1:"D";}s:1:"B";a:3:{i:0;s:1:"E";i:1;s:1:"N";i:2;s:1:"Y";}s:1:"W";a:2:{i:0;s:1:"J";i:1;s:1:"Y";}s:1:"G";a:2:{i:0;s:1:"A";i:1;s:1:"K";}s:1:"J";a:1:{i:0;s:1:"T";}s:1:"X";a:1:{i:0;s:1:"H";}s:1:"E";a:1:{i:0;s:1:"Z";}s:1:"N";a:1:{i:0;s:1:"B";}s:1:"Z";a:2:{i:0;s:1:"A";i:1;s:1:"M";}s:1:"U";a:1:{i:0;s:1:"R";}s:1:"F";a:2:{i:0;s:1:"C";i:1;s:1:"V";}s:1:"I";a:1:{i:0;s:1:"F";}s:1:"C";a:3:{i:0;s:1:"O";i:1;s:1:"P";i:2;s:1:"T";}s:1:"Q";a:2:{i:0;s:1:"L";i:1;s:1:"V";}s:1:"Y";a:1:{i:0;s:1:"C";}s:1:"K";a:3:{i:0;s:1:"T";i:1;s:1:"P";i:2;s:1:"A";}s:1:"A";a:1:{i:0;s:1:"J";}s:1:"M";a:1:{i:0;s:1:"W";}s:1:"R";a:1:{i:0;s:1:"I";}s:1:"P";a:2:{i:0;s:1:"K";i:1;s:1:"N";}s:1:"O";a:1:{i:0;s:1:"G";}s:1:"H";a:1:{i:0;s:1:"Q";}s:1:"D";a:1:{i:0;s:1:"U";}}
Это означает…
V
можно пойти в S
L
можно пойти в M
, Z
а также G
S
можно пойти в T
, X
а также K
Мне нужен алгоритм, чтобы найти кратчайший путь от A
в Z
, Этот способ должен быть сохранен в виде списка узлов, что-то вроде AJTDURIFCPNBEZ
,
Я только что попробовал это с этой рекурсией:
function getWays($key = "A") {
global $roads;
echo $key;
if($key == "Z"){
echo "<br />";
return;
}
foreach($roads[$key] as $next)
if($next != "A")
getWays($next);
}
Это не работает, это намного сложнее. Вы должны предотвратить петли и увеличить производительность (игнорируйте длинные пути раньше, если вы уже нашли более короткие).
Кто-нибудь может оказать помощь?
Задача ещё не решена.
Других решений пока нет …