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

Question

У меня есть невзвешенный график DAG.Что я хочу сделать, так это найти все пути жадным образом, и путь должен содержать как минимум K узлов и заданный начальный узел.

Существует ли какой-либо существующий алгоритм / имплементация, который это делает?*

Например, у меня есть следующий график:

my %graph =(36=>[31],31=>[30,22],30=>[20],22=>[20,8],20=>[1],8=>[5],5=>[2],2=>[1,20]);

Поэтому, если я определю K = 5 и начальный узел 36, я надеюсь получить:

{1,20,22,31,36}
{1,20,2,5,8,22,31,36}
{1,20,30,31,36}
{1,2,5,8,22,31,36}

Answer 1

Это не очень сложно.

use warnings;
use strict;
use Data::Dumper;

my @stack = ();

my %graph = (36=>[31],31=>[30,22],30=>[20],22=>[20,8],
             20=>[1],8=>[5],5=>[2],2=>[1,20]);

# add begin to stack
push(@stack, { node => 36, way => [36] });

while (@stack > 0) {

    my $node = pop(@stack);

    # way
    my $way = $node->{way};

    # complete way
    if ($node->{node} == 1) {
        print Dumper($node->{way});
    }

    # add next nodes
    my $nextArr = $graph{$node->{node}};

    for my $nextNod (@$nextArr) {
        # add way
        my @tmpWay = @$way;
        push(@tmpWay, $nextNod);

        # add to stack
        push(@stack, { node => $nextNod, way => \@tmpWay });
    }
}

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

edit

Добавить бесконечную защиту сохранения.

edit 2

Вам не нужна бесконечная защита.Добавьте shift к pop, тогда вы ищете несколько способов завершить заметку:)