Recherche de trajectoires dans un graphe orienté avec approche gourmande avec au moins K nœuds et un nœud de départ donné

Question

J'ai un graphe DAG non pondéré. Ce que je veux faire est de trouver tous les chemins d'une manière gourmande et le chemin doit contenir au moins K nœuds, et un nœud de départ donné.

Y a-t-il un algorithme/une implémentation existant qui fait cela?

Par exemple, j'ai le graphique suivant:

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

Donc, si je définis K = 5 et noeud de départ 36, j'espère obtenir:

{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

Ce n'est pas très difficile.

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

Vous pouvez donc tester, si le nœud est le noeud final et enregistrer tous les chemins. Vous devez Optimase ce script

modifier

Ajout sans fin sauver la protection.

éditer 2

Vous n'avez pas besoin d'une protection sans fin. Ajouter shift à pop, puis vous cherchez plus d'un moyen de mettre fin à la note :)