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.
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 .
fuente
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(a→b) (a→b) s t
A partir de , realice lo siguiente:b:=t
Si ya se visitó , devuelva los valores min ( b ) y max ( b ) ya calculados . De lo contrario, marque b como visitado.b min(b) max(b) b
Determine y registre y max ( b ) de la siguiente manera.min(b) max(b)
fuente