Problème de programmation python

[PacoAzevedo]

Bonjour à tous, dans le cadre d'un projet je suis amené a résoudre le problème suivant:

Je dispose d'un graphe dont la matrice associée est uniquement composée de 0 et de 1, qui est triangulaire supérieur et dont tous les coefficients diagonaux sont nulles
Ce graphe représentant un ensemble de villes, on cherche le nombre de chemins menant de la ville de départ (étant fixée comme la ville n°0) à la ville d'arrivée (étant fixée comme la ville n°x-1 ou x représente la dimension de la matrice)
Je dispose déjà d'un algorithme permettant de compter le nombre de chemins
(en additionnant successivement les coefficients "supérieur droit" des puissances successives de la matrice associée)
Cependant il m'est nécessaire de pouvoir énumérer ces chemins et ne pas seulement pouvoir en compter le nombre

Exemple: 0 1 2 3
0 [0 1 1 0]
1 [0 0 1 1]
2 [0 0 0 1]
3 [0 0 0 0]

Voici la matrice associée d'un graphe a 4 points, mon programme m'informe qu'il y a 3 chemins différents pour se rendre de 0 vers 3 cependant il me serait nécessaire de créer un programme qui me renseigne sur les chemins en question a soir dans l'exemple : 0->1->3
0->2->3
0->1->2->3


Et c'est sur ce point précis que je bloque complètement, j’espère ainsi avoir quelques pistes de réflexion sachant néanmoins que je suis très loin de maitriser le langage python a la perfection

Merci d'avance pour vos réponse
-----

[invite73192618]

C'est difficile de répondre sans ton code.

[PacoAzevedo]

Le programme que j'ai pour l'instant est assez simple et il permet seulement de dénombrer le nombre de chemins d'un graphique donné

def Chemins(C):
a=0
n=len(C)
A=C
for k in range(n):
a += A[0][n-1]
A=produit(A,C)
return a

[Tryss2]

Voici un algorithme récursif qui marche si toutes les villes sont accessibles à partir de celle de départ (sinon, il faut faire un petit pré-traitement du graphe).

fonction EnumereChemin(chemin)
    etape = debut chemin
    si etape == départ alors
        afficher chemin
    sinon
        pour chaque ville menant à etape
            EnumereChemin( ville+chemin )
        fin pour
    fin si        
fin fonction

Pour l'implémenter en Python, il y a une subtilité : bien faire attention à passer une copie de la liste chemin à chaque fois (sinon, la liste originale est modifiée dans les appels suivants de fonction)

[A voir en vidéo sur Futura]

[invite73192618]

def Chemins(C):
    a=0
    n=len(C)
    A=C
    for k in range(n):
        a += A[0][n-1]
        A=produit(A,C)
    return a

Tu peux citer ce message pour voir comment ajouter les balises code. Ok, moi non plus jenevois pas comment modifier cela pour tes besoins, et moi aussi j'irais avec une solution comme celle de Tryss2, qui est particulierement elegante avec son appel recursif a elle-meme (un bemol, le cas de boucles ne sont pas exclues par son pseudo-code).

[Tryss2]

(un bemol, le cas de boucles ne sont pas exclues par son pseudo-code).

J'ai considéré que le graphe était orienté, et vu que la matrice est triangulaire supérieure, pas de boucles possibles. Au passage, dès qu'il y a une boucle, le nombre de chemin est infini

[invite73192618]

Oui, c'est ce que je voulais dire : sans garde-fou l'utilisateur doit se rappeler de ne pas envoyer une matrice hors postulats, sinon le code pourrait prendre un temps long, surtout vers la fin

[PacoAzevedo]

Merci beaucoup pour le pseudo-code, toutefois il me semble qu'il dépend d'un chemin donné il serait donc nécessaire d'appliquer le programme a chacune des villes directement liées a la ville d'arrivée ?
En prenant l'exemple de la matrice que j'ai donné dans mon premier message, pour obtenir l'ensemble des chemins il est nécessaire d'appliquer le programme au chemin 3->4
et au chemin 2->4 sans quoi des chemins ne seront pas dénombrés

[invite73192618]

C'est toute la beauté de ce code: si EnumereChemin trouve que la destination (4) n'est pas immédiate, alors il lance EnumereChemin pour les destinations immédiatement précédentes donc EnumereChemin(2) et EnumereChemin(3), et ainsi de proche en proche tous les chemins finissent par être explorés sur toute leur longueur.