Modificato percorso più breve utilizzando l'algoritmo di Dijkstra o Bellman-Ford

Question

Come possiamo usare l'algoritmo di Bellman-Ford di Dijkstra o per trovare il percorso più breve in un grafico il cui alcuni dei bordi sono colpiti se andiamo vertici specifici. Tale che, la lunghezza del bordo interessata sarà superiore o inferiore alla lunghezza originale.

Answer 1

Se ho capito questo diritto, si vuole cambiare il costo di un bordo in un grafico a seconda di nodi che vengono visitati nel percorso corrente. Un esempio dai commenti è:

"Bordo AB ha lunghezza 3, ma se anche si visita il nodo C, la lunghezza di AB sarà 5"

Ora, non sembra essere un modo per qualcosa come l'algoritmo di Djikstra da utilizzare in quanto v'è un passo avido in tale algoritmo che raccoglie il nodo 'migliore' in ogni fase. L'idea che il nodo 'migliore' a quel punto può cambiare in un secondo tempo (a causa di una norma come sopra) viola il concetto di approccio greedy che presuppone che stiamo effettivamente visitando nodi in ordine dal migliore al peggiore costo. Io non sono certo se questo è NP difficile come suggerito, ma certamente non può utilizzare una sorta di Dijikstra approccio fin dall'inizio. +1 per il problema però.