Plus long chemin à partir d'un noeud donné dans un graphe cyclique

Bonjour, Je voulais savoir s’il y avait une manière simple de modifier un BFS afin de trouver le plus long chemin à partir d’un noeud donné (passant au plus une fois par le même noeud) dans un graphe pouvant comporter des cycles. J’ai pensé au code suivant mais qui ne fonctionne pas…

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def bfs(lst):
    global etat,dist
    if lst == []:
        return
    nxt = []
    for i in range(0,len(lst)):
        if len(voisins(lst[i]))==0:
            etat[lst[i]]=0
        for elem in voisins(lst[i]):
            if etat[elem]!=1:
                etat[elem]=1
                nxt.append(elem)
                dist[elem]=max(dist[elem],dist[lst[0]]+1)
    bfs(nxt)

Merci d’avance pour vos réponses

Regardes l’algorithme de Bellman-Ford.

Mais l’algorithme de Bellmann Ford fonctionne avec les plus courts chemins non ? on mettrait alors tous les poids à -1 sur les arcs ?

Ah oui, pardon, j’ai lu trop vite. Je suis désolé. Ton problème n’a pas de solution polynomiale connue. Tu peux trouver plein d’infos en cherchant « longest path problem ». Il existe des solutions approchées.

Ah dommage… Merci pour ta réponse !

Je dirais plutôt qu’il n’y à pas de solution. Si j’ai bien compris le problème, tu cherche à trouver le plus long chemin possible dans un graphe qui comporte des cycle. Si c’est le cas bah… tu peux bouclé à l’infini donc la solution serais un truc du genre $+\infty$

Il ne faut pas passer deux fois par le même nœud. J’avais aussi raté ça en première lecture.