<<<На главную
Поиск всех путей на ориентированном графе из точки а в точку f
на основе упорядочивания массивов и элементов массива по возрастанию.
Легко доработать до поиска кратчайшего пути.
Ориентированный граф с 6 вершинами:
В текстовом представлении:
a → b, a → c, a → d
b → d, b → e, b → f
c → d, c → e, c → f
d → e, d → f
e → f
f → (нет исходящих)
Код на языке PHP:
https://gitflic.ru/project/dcc0/mix-c-89-php/blob/?file=all_ways_three_matrix.php
Результат:
Array
(
[0] => a
[1] => b
[2] => d
[3] => e
[4] => f
)
Array
(
[0] => a
[1] => b
[2] => d
[3] => f
)
Array
(
[0] => a
[1] => b
[2] => e
[3] => f
)
Array
(
[0] => a
[1] => b
[2] => f
)
Array
(
[0] => a
[1] => c
[2] => d
[3] => e
[4] => f
)
Array
(
[0] => a
[1] => c
[2] => d
[3] => f
)
Array
(
[0] => a
[1] => c
[2] => e
[3] => f
)
Array
(
[0] => a
[1] => c
[2] => f
)
Array
(
[0] => a
[1] => d
[2] => e
[3] => f
)
Array
(
[0] => a
[1] => d
[2] => f
)
Все пути:
Array
(
[0] => Array
(
[0] => a
[1] => b
[2] => d
[3] => e
[4] => f
)
[1] => Array
(
[0] => a
[1] => b
[2] => d
[3] => f
)
[2] => Array
(
[0] => a
[1] => b
[2] => e
[3] => f
)
[3] => Array
(
[0] => a
[1] => b
[2] => f
)
[4] => Array
(
[0] => a
[1] => c
[2] => d
[3] => e
[4] => f
)
[5] => Array
(
[0] => a
[1] => c
[2] => d
[3] => f
)
[6] => Array
(
[0] => a
[1] => c
[2] => e
[3] => f
)
[7] => Array
(
[0] => a
[1] => c
[2] => f
)
[8] => Array
(
[0] => a
[1] => d
[2] => e
[3] => f
)
[9] => Array
(
[0] => a
[1] => d
[2] => f
)
)
Количество всех путей 10
Расстояния
Array
(
[ab] => 1
[ac] => 2
[ad] => 3
[bd] => 1
[be] => 1
[bf] => 3
[cd] => 1
[ce] => 1
[cf] => 1
[de] => 2
[df] => 1
[ef] => 4
)
Минимальное расстояние = 3
Для пути:
Array
(
[0] => a
[1] => b
[2] => d
[3] => f
)