Получить кратчайший путь через узлы

У меня есть этот массив:

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);
}

Это не работает, это намного сложнее. Вы должны предотвратить петли и увеличить производительность (игнорируйте длинные пути раньше, если вы уже нашли более короткие).

Кто-нибудь может оказать помощь?

0

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]