Correttezza dell'algoritmo Bellman-Ford, possiamo ancora fare meglio?

Question

Ho saputo che l'algoritmo Bellman-Ford ha un tempo di esecuzione di O (| E | * | V |), in cui l'E è il numero di bordi e il numero di vertici.Assumi che il grafico non abbia cicli negativi ponderati.

La mia prima domanda è che come dimostriamo che all'interno (| v | -1) iterazioni (ogni iterazione controlla ogni bordo in E), aggiorna il percorso più breve per ogni nodo possibile, dato un particolare nodo iniziale?È possibile che abbiamo iterato (| v | -1) volte ma non finiscono ancora con percorsi più corti per ogni nodo?

Assumi la correttezza dell'algoritmo, possiamo effettivamente fare meglio di così?Si verifica che non tutti i bordi sono ponderati negativamente in un particolare grafico.L'algoritmo Bellman-Ford sembra costoso, come ogni iterazione passa attraverso tutti i bordi.

Answer 1

Il percorso più lungo possibile dalla fonte a qualsiasi vertice comporterebbe al massimo tutti gli altri vertici nel grafico. In altre parole - non avrai un sentiero che attraversa la stessa vertice più di una volta, poiché ciò aumenterebbe necessariamente i pesi (questo è vero solo grazie al fatto che non ci sono cicli negativi).
Su ogni iterazione aggiornare il peso del percorso più breve sul prossimo vertice in questo percorso, fino a dopo | V | -1 Iterazioni I tuoi aggiornamenti dovrebbero raggiungere la fine di quel percorso. Dopo che non ci saranno vertici con valori non stretti, dal momento che il tuo aggiornamento ha coperto tutti i percorsi più brevi fino a quella lunghezza.

Questa complessità è stretta (almeno per BF), pensa a una lunga linea di vertici collegati. Scegli il più a sinistra come la fonte - il tuo processo di aggiornamento dovrebbe funzionare da lì dall'altra parte una volta Vertice alla volta. Ora potresti discutere di non dover controllare ogni bordo in quel modo, quindi buttiamo in alcuni bordi casuali con un peso molto grande (n> | v | * peso massimo) - non possono aiutarti, ma Il tuo algoritmo non può sapere di sicuro, quindi se deve passare attraverso il processo di aggiornamento dei vertici con questi pesi (sono ancora migliori dell'infinito iniziale).