Finding Paths in Directed Graph with Greedy Approach With At Least K Nodes and a Given Starting Node

Question

I have a non-weighted DAG graph. What I want to do is to find all the paths in a greedy way and the path should contain at least K nodes, and a given starting node.

Is there any existing algorithm/implmentation that does that?

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 starting 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

That's not very dificult.

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 test, if node the end node and save all path (ways) out. You must optimase this script

edit

Add endless save protection.

edit 2

You don't need a endless protection. Add shift to pop, then you search more than one way to end note :)