Finding paths on a graph with a greedy approach with the smallest value of K Node s and a given launch of Node

Question

I have a non-weighted DAG chart. I want to do to find all the paths in the greedy path and the path must contain at least K nodes, and the given node start.

Is there any existing algorithm / implication that does this?

For example, I have the following graph:

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

So, if I define K = 5 and start node 36, I hope to get:

{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

This is not very bad.

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

So you can check if node is the end of node and save all paths (paths). You must optimize this script

Edit

Add endless save protection.

change 2

. shift pop, :)