Recherche des chemins les plus courts et les plus longs entre deux sommets dans un DAG

14

Étant donné un DAG non pondéré (graphique acyclique dirigé) D=(V,A) et deux sommets et , est-il possible de trouver le chemin le plus court et le plus long de à en temps polynomial? Les longueurs de trajet sont mesurées par le nombre d'arêtes.stst

Je suis intéressé à trouver la gamme de longueurs de trajet possibles en temps polynomial.

Ps., Cette question est un double de la question StackOverflow Chemin le plus long dans un DAG .

robowolverine
la source

Réponses:

10

Pour le problème de chemin le plus court, si nous ne nous soucions pas des poids, la recherche de largeur en premier est un moyen infaillible. Sinon, l'algorithme de Dijkstra fonctionne tant qu'il n'y a pas de bords négatifs.

Pour le chemin le plus long, vous pouvez toujours faire Bellman-Ford sur le graphique avec tous les poids de bord annulés. Rappelez-vous que Bellman-Ford fonctionne tant qu'il n'y a pas de cycles de poids négatifs, et fonctionne donc avec tous les poids sur un DAG.

jmite
la source
2
Bellman-Ford est un algorithme de programmation dynamique.
Raphael
1
@Raphael oui, mais je pense qu'il y a un algorithme DP direct pour trouver le chemin max, au lieu de nier tous les poids de bord.
jmite
1
@jmite: Pourquoi, bien sûr: il suffit de changer Bellman-Ford pour faire la conversion en ligne, ou de maximiser, ou ...
Raphael
1
Soit dit en passant, je ne suis pas intuitivement convaincu que le problème NP-complet Longest Path se trouve donc facilement dans P sur les DAG. J'apprécierais une preuve / référence / explication.
Raphael
2
Il existe également un algorithme DP plus simple et efficace pour DAG
8

n=|V(G)|m=|E(G)|w(ab)(ab)st

b:=t

  1. bmin(b)max(b)b

  2. min(b)max(b)

    • b=smin(s):=max(s):=0
    • min(b):=minab[w(ab)+min(a)]max(b):=maxab[w(ab)+max(a)]
      min(a)=max(a)=inaccessiblebmin(b):=max(b):=inaccessible

O(m)

Niel de Beaudrap
la source
Cette approche «pull» récursive peut être en réalité plus lente que l'approche «push» dynamique habituelle et elle nécessite une pile de taille linéaire pour gérer la récursivité. L'approche habituelle est de prendre des sommets dans un ordre topologique et d'améliorer le minimum et le maximum provisoires pour chaque voisin du nœud courant. Le nœud actuel a toujours la valeur finale de minimum et maximum car tous les bords entrants doivent avoir déjà été utilisés pour les améliorer.
Palec