Bellman Ford e One Olympiad Questions?

Question

Ho fatto un esame olimpico tre giorni fa. Mi sono imbattuto in una bella domanda come segue.

Sappiamo algoritmi facchino-guado controllare tutti i bordi di ogni fase, e per ciascun bordo se,

d (v)> d (u) + w (u, v)

poi d(v) essendo aggiornato in modo tale che w(u,v) è il peso del bordo (u, v) e d(u) è la lunghezza del percorso di ricerca migliore per vertice u. se in un passo abbiamo no update for vertexes, gli algoritmi terminate. supponendo che questi algoritmi, per trovare il percorso più breve dal vertice s nel grafico G con il vertice n dopo lo k < n, l'iterazione sia terminata, quale delle seguenti è corretta?

1) numero di lati in tutti i percorsi più brevi dal s è al massimo k-1

2) peso di tutti i percorsi più brevi dal s è al massimo k-1

3) Graph non ha ciclo negativo.

Chi può discutere di queste opzioni?

Answer 1

1 non è corretto, perché se ci capita di rilassare gli archi nell'ordine topologico di un albero del percorso più breve, allora convergeremo in un'unica iterazione, nonostante il fatto che l'albero del percorso più breve possa essere arbitrariamente profondo.

s --> t --> u --> v 

Relax s->t, t->u, u->v; shortest path from s->v is three hops, 
but B--F has made two iterations. 

Se facciamo il rilassamento simultaneamente (cioè, utilizzare sempre i valori da rotondo r-1 in R turno, anche se r intorno ad essi ha aggiornato), quindi 1 è effettivamente corretto, per induzione (la profondità l'albero del percorso più breve inizia da zero e cresce al massimo uno in ogni round che non è l'ultimo).

2 non è corretto, perché chissà quali sono i pesi?

100 
s --> t 

Relax s->t; weight is 100, but B--F has made two iterations. 

3 è corretto, perché con un argomento di calcolo della media almeno un arco di un ciclo negativo non sarebbe rilassato. Lascia che sia v1, ..., vn un ciclo. Poiché gli archi sono rilassati, abbiamo d(vi) + len(vi->vi+1) - d(vi+1) >= 0. Sommare le disuguaglianze per tutti i i e telescopare i termini d per semplificare a sum_i len(vi->vi+1) >= 0, che dice che il ciclo è non negativo.

Answer 2

penso che l'opzione 3 non sia corretta in quanto per sapere se esiste un ciclo di peso negativo, l'algoritmo di Ford for Bellman deve essere eseguito n volte. prima n-1 volte per calcolare il percorso più breve e poi ancora una volta per verificare se c'è qualche miglioramento nelle distanze se ci sono miglioramenti, significa che c'è un ciclo di peso negativo.