grafico - Dijkstra per il singolo-Source percorso più lungo

Ok, ho postato questa domanda perché di questo esercizio:grafico - Dijkstra per il singolo-Source percorso più lungo

Possiamo modificare l'algoritmo di Dijkstra per risolvere il single-source problema più lungo percorso modificando minimo al massimo? Se è così, prova che il tuo algoritmo è corretto. In caso contrario, fornire un controesempio.

Per questo esercizio o tutto ciò che riguarda l'algoritmo di Dijkstra, presumo non ci sono pesi negativi nel grafico. Altrimenti, non ha molto senso, poiché anche per il problema del percorso più breve, Dijkstra non può funzionare correttamente se esiste un margine negativo.

Ok, la mia intuizione ha risposto per me:

Sì, penso che può essere modificato.

Ho appena

inizializzazione array di distanza per MININT
cambiamento distance[w] > distance[v]+weight a distance[w] < distance[v]+weight

Poi ho fatto qualche ricerca per verificare la mia risposta. Ho trovato questo post:

Longest path between from a source to certain nodes in a DAG

Per prima cosa ho pensato che la mia risposta era sbagliata a causa del post di cui sopra. Ma ho scoperto che forse la risposta nel post qui sopra è sbagliata. È stato modificato Il problema di percorso più lungo della singola origine con Il problema del percorso più lungo.

Anche nel wiki di Bellman–Ford algorithm, esso detta correttamente:

L'algoritmo di Bellman-Ford calcola sorgente unica percorsi più brevi in un grafo orientato ponderata. Per i grafici con solo spigoli di bordo non negativi, l'algoritmo di Dijkstra più veloce risolve anche il problema. Pertanto, Bellman-Ford viene utilizzato principalmente per i grafici con pesi negativi.

Quindi penso che la mia risposta sia corretta, giusto? Dijkstra può davvero essere Il problema di percorso più lungo di e le mie modifiche sono anche corrette, giusto?

fonte

2012-05-05 Jackson Tale

@Kristo, puoi dare un'occhiata? –

No, non possiamo - o per lo meno, non polinomiale riduzione/modifica è noto - è longest path problem NP-Hard, mentre dijkstra viene eseguito in tempo polinomiale!

Se possiamo trovare un modfication per dijsktra per rispondere a problemi più lungo percorso in tempo polinomiale, possiamo derivare P=NP

In caso contrario, quindi fornire un controesempio.

Questo è un compito molto brutto. L'esempio del contatore può fornire una modifica specifica errata, mentre potrebbe esserci una modifica diversa che è OK.
La verità è che non sappiamo se il problema del percorso più lungo sia risolvibile in tempo polinomiale o meno, ma l'ipotesi generale è - non lo è.

per quanto riguarda solo cambiando il passo relax:

 A 
    /\ 
     1 2 
    / \ 
    B<--1---C 
edges are (A,B),(A,C),(C,B)

Dijkstra da una volontà prima scelta B, e quindi B non è mai raggiungibile - perché è fuori del set di distances.

Per lo meno, si dovrà anche modificare l'heap minimo nell'heap massimo, ma avrà un diverso esempio di contatore perché non riesce.

(1), probabilmente, forse se P = NP è possibile, ma è molto improbabile.

fonte

2012-05-05 14:25:23 amit

amit, questo è quello di cui stavo parlando nella mia domanda. Penso che il problema del percorso più lungo sia diverso dal problema del percorso più lungo con origine singola. Nel "Problema del percorso più lungo", dobbiamo trovare il singolo percorso più lungo nell'intero grafico. Ma nella mia domanda sopra, "single sourced" significa che ci viene dato un vertice S, quindi scoprire quale percorso è più lungo orientato da S. Sono problemi diversi, giusto? –

ah, ok, penso di aver fatto un errore. Se il problema del percorso più lungo può essere risolto da solo, allora per ogni vertice facciamo il percorso più lungo a sorgente singola, quindi li confrontiamo tutti, quindi risolviamo il problema del percorso più lungo. Questo non è possibile in quanto il problema del percorso più lungo è NP. ok, immagino cosa ho pensato di sbagliato. –

puoi forse usare parole più semplici per descrivere perché il problema del percorso più lungo non può essere risolto se sostituisco MIN con MAX in Dijkstra? –

Sì, possiamo. E la tua risposta è quasi corretta. Tranne una cosa

Si presuppone senza pesi. In questo caso l'algoritmo di Dijkstra non riesce a trovare il percorso più lungo.

Ma se si assumono i pesi negativi , è possibile trovare facilmente il percorso più lungo. Per provare la correttezza, basta prendere i valori assoluti di tutti i pesi e si ottiene esattamente il solito algoritmo di Dijkstra con pesi positivi.

fonte

2012-05-05 14:45:27

Penso che la tua risposta stia facendo un trucco. Se assumo solo pesi negativi, il percorso più lungo è come "il percorso più breve in tutti i pesi positivi". Non penso che sia ciò che l'accisa sta cercando. –

@JacksonTale, sì, questo è solo un trucco. Ma non è chiaro dal testo delle accise, cosa significa. Altrimenti, la risposta di amit è molto buona. –

Grazie per la risposta. Immagino che cosa significhi realmente l'accisa per il vero problema del percorso più lungo. Il mio male per aggiungere una tale ipotesi. –

Funziona in grafici aciclici diretti ma non in grafici ciclici. Dal momento che il percorso sarà tracciato e non c'è modo di evitarlo nell'algo di dijkstra

fonte

2013-10-13 18:13:32 Wolf7176

grafico - Dijkstra per il singolo-Source percorso più lungo

risposta

Problemi correlati