Création d'un programme pour trouver le chemin le plus long

Question

Je suis relativement novice en programmation et j'ai quelques problèmes. Fondamentalement je dois faire une fonction qui trouvera les longueurs de tous les chemins à travers un diagramme de réseau. J'ai travaillé dessus pendant des heures mais je n'arrive pas à aller nulle part. En utilisant la récursivité je peux naviguer à travers tous les chemins, mais je ne suis pas sûr de la façon dont je devrais enregistrer la longueur des chemins.

Toute aide serait grandement appréciée. Merci!

Edit: En savoir plus. Le tableau dependencies est les dépendances pour chaque chemin sur le réseau. Ainsi, le chemin six est lié aux chemins 4 et 2, le chemin 5 est aligné sur le chemin 3, etc. Les durées sont les durées que prend chaque chemin, donc le chemin 6 prend 10 heures, le chemin 5 prend 9 heures, etc

Les chemins 1,2 et 3 sans dépendance se développent à partir d'un point de départ et les chemins 5 et 6 qui ne dépendent pas de tous convergent vers un point final. Je dois donc trouver les durées de toutes les voies du début à la fin. L'approche que j'ai prise jusqu'ici va du point final au point de départ et à ce stade mon code peut trouver tous les chemins, j'ai juste beaucoup de mal à comprendre comment enregistrer toutes les durées séparément. Merci.

$dependencies = array("","","","1","3","4,2"); 
$durations = array("5","3","4","11","9","10"); 


function tracePath($path,$dependencies,$durations,$returnArray=array()) { 

    if($dependencies[$path] != "") { 
     $currentTaskDependencies = preg_split("/[\s]*[,][\s]*/", $dependencies[$path]); 

     for($i=0;$i<count($currentTaskDependencies);$i++) { 
      tracePath($currentTaskDependencies[$i]-1,$dependencies,$durations,$returnArray[$i]); 
     }  
    } 
    return $returnArray; 
} 

tracePath(6,$dependencies,$durations); 

Answer 1

Pourquoi avez-vous besoin de trouver tous les chemins imaginables? Le titre de votre question indique que vous cherchez le chemin le plus long, donc c'est tout simplement l'inverse d'un algorithme de chemin le plus court, donc Algorithme de Djikstra http://en.wikipedia.org/wiki/Dijkstra 's_algorithm ou Floyd Warshall http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm (comme déjà mentionné).