Trouver le plus long chemin dans un dirigé cyclique graphique à partir d'une source s vers une destination f.Supposons pas d'effet positif de poids cycles existe

Question

je dois Trouver le plus long chemin dans un dirigé cyclique graphique à partir d'une source s vers une destination f.Supposons pas d'effet positif de poids cycles existe même si aucun élément de poids cycles existent, les cycles de 0 ou de poids est négatif n'existe pas.Quelqu'un peut-il proposer un algorithme pour trouver le plus long chemin dans ce cas.merci de citer la source si possible.

merci

Answer 1

Je ne suis pas sûr si cela va fonctionner (besoin de vérifier), mais...vous pouvez faire quelque chose de similaire à:

Laissez min = min weight on the graph.
max = max weight on the graph.
Définir les nouveaux coefficients de pondération pour toutes les arêtes = wNew(e) = max - (wOld(e)-min).

Maintenant, il y a de négatif revenants et les poids sont dans l'ordre inverse (sens si w(e1) était plus grand que w(e2) il est maintenant plus petit).

Que faire si nous avons maintenant rechercher le chemin le plus court?

Answer 2

Nier simplement vos poids de bord et exécutez un algorithme de chemin le plus court (par exemple, Bellman-Ford).

Les cycles de poids zéro pourraient être un problème. Vous devrez rompre les liens sur vos chemins en choisissant le plus court (en longueur, pas en poids). Une façon de le faire est de faire en sorte que vos poids soient une paire (- (poids d'origine), 1), de les ajouter par paire et de faire la commande lexicographique.

Voir également Le plus long chemin entre deux sommets

Answer 3

Si vous avez un DCG, vous pouvez simplement faire bouclez pour toujours avant d'atteindre votre cible, ce serait le "chemin le plus long". Dans ce cas, la question est incomplète et l'algorithme semble probablement différent en fonction des détails.

Cela ressemble à des devoirs.