Encontrar caminos más cortos y más largos entre dos vértices en un DAG

14

Dado un DAG no ponderado (gráfico acíclico dirigido) y dos vértices s y t , ¿es posible encontrar el camino más corto y más largo de s a t en tiempo polinómico? Las longitudes de camino se miden por el número de aristas.D=(V,A)stst

Estoy interesado en encontrar el rango de posibles longitudes de ruta en tiempo polinómico.

Ps., Esta pregunta es un duplicado de la pregunta StackOverflow La ruta más larga en un DAG .

robowolverine
fuente

Respuestas:

10

Para el problema de la ruta más corta, si no nos interesan los pesos, entonces la búsqueda de amplitud es una forma segura. De lo contrario, el algoritmo de Dijkstra funciona siempre que no haya bordes negativos.

Para el camino más largo, siempre puede hacer Bellman-Ford en el gráfico con todos los pesos de borde negados. Recuerde que Bellman-Ford funciona siempre que no haya ciclos de peso negativos y, por lo tanto, funciona con cualquier peso en un DAG.

jmite
fuente
2
Bellman-Ford es un algoritmo de programación dinámico.
Raphael
1
@Raphael sí, pero creo que hay un algoritmo DP directo para encontrar la ruta máxima, en lugar de negar todos los pesos de borde.
jmite
1
@jmite: ¿Por qué, por supuesto? Simplemente cambie Bellman-Ford para hacer la conversión en línea, o maximice, o ...
Raphael
1
Por cierto, no estoy intuitivamente convencido de que el problema NP-complete Longest Path esté fácilmente en P en DAG. Agradecería una prueba / referencia / explicación.
Raphael
2
También hay un algoritmo DP más simple y eficiente para DAG
8

Deje y m = | E ( G ) | . Deje w ( a b ) denotar el peso del borde ( a b ) . Suponga que desea encontrar el costo de ruta mínimo y máximo de s a t .n=|V(G)|m=|E(G)|w(ab)(ab)st

A partir de , realice lo siguiente:b:=t

  1. Si ya se visitó , devuelva los valores min ( b ) y max ( b ) ya calculados . De lo contrario, marque b como visitado.bmin(b)max(b)b

  2. Determine y registre y max ( b ) de la siguiente manera.min(b)max(b)

    • Si , almacene min ( s ) : = max ( s ) : = 0 .b=smin(s):=max(s):=0
    • Else establece
      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) , descuidando el tiempo requerido para inicializar todas las variables de vértice.

Niel de Beaudrap
fuente
Este enfoque recursivo de "atracción" podría ser en realidad más lento que el enfoque de "empuje" dinámico habitual y necesita una pila de tamaño lineal para manejar la recursividad. El enfoque habitual es tomar los vértices en un orden topológico y mejorar el mínimo y el máximo provisionales para cada vecino del nodo actual. El nodo actual siempre tiene el valor final de mínimo y máximo, ya que todos los bordes entrantes ya deben haberse utilizado para mejorarlos.
Palec