Trova il percorso più lungo in un grafico ciclico diretto da una sorgente s a una destinazione f. Supponiamo che non esistano cicli di peso positivo

Question

Devo trovare il percorso più lungo in un grafico ciclico diretto da una fonte S a una destinazione f. Supponiamo che non esistano cicli di peso positivo anche se esistono cicli di peso positivo, esistono cicli di 0 o pesi negativi. Qualcuno può suggerire un algoritmo per trovare il percorso più lungo in questo caso. Si prega di citare la fonte, se possibile.

Grazie

Answer 1

Non sono sicuro che questo funzionerà (è necessario controllarlo) ma ... puoi fare qualcosa di simile a:

Permettere min = min weight on the graph.
max = max weight on the graph.
Imposta nuovi pesi per tutti i bordi = wNew(e) = max - (wOld(e)-min).

Ora ci sono wight negativi e i pesi sono in ordine inverso (che significa se w(e1) era più grande di w(e2) ora è più piccolo).

E se ora cerchiamo il percorso più breve?

Answer 2

Basta annullare i pesi del bordo e eseguire un algoritmo di percorso più breve (ad es. Bellman-Ford).

I cicli di peso zero potrebbero essere un problema. Dovrai rompere i legami sui tuoi percorsi raccogliendo quello più corto (di lunghezza, non di peso). Un modo per farlo è rendere i tuoi pesi una coppia (-(peso originale), 1), aggiungerli a coppie e fare l'ordinamento lessicografico.

Guarda anche Percorso più lungo tra due vertici

Answer 3

Se hai un DCG, puoi semplicemente loop per sempre prima di arrivare al tuo obiettivo, sarebbe il "percorso più lungo". In tal caso, la domanda è incompleta e l'algoritmo probabilmente sembra diverso a seconda delle specifiche.

Sembra i compiti.