Output di codice su grafico e alcune affermazioni sul concorso locale?

Question

Mi sono imbattuto in una domanda come segue:

Abbiamo un codice su grafico ponderato, acicliche G(V, E) con bordi positivi e negativi. cambiamo il peso di questo grafico con il seguente codice, per dare un G senza margine negativo (G'). se V={1,2...,n} e G_ij essere un peso del bordo i a bordo j.

Change_weight(G) 
for i=i to n 
    for j=1 to n 
     c_i=min c_ij for all j 
     if c_i < 0 
      c_ij = c_ij-c_i for all j 
      c_ki = c_ki+c_i for all k 

Abbiamo due assiomi:

1) il percorso più breve tra ogni due vertici in G è uguale a G'.

2) la lunghezza del percorso più breve tra ogni due vertici in G è la stessa di G '.

Vogliamo verificare queste due frasi. quale è Vero e quale è falso Chi può aggiungere qualche indicazione sul perché questi sono vere o false?

mia soluzione:

Credo due è falso come seguendo contro esempio, il grafico originale è dato a sinistra, e dopo l'algoritmo viene eseguito, il risultato è proprio il percorso più breve tra 1 a 3 cambiato, è passato dal vertice 2, ma dopo l'algoritmo viene eseguito non è mai passato da vertice 2.

Answer 1

Ipotesi:

ci sono alcuni problemi con r presentazione della domanda; Ho fatto alcune ipotesi, che chiarisco qui. La risposta alla tua domanda, dato che queste ipotesi sono corrette, è nella sezione sottostante.

Primo, come ha detto @amit, l'utilizzo di j non è chiaro. Sembra che volevi dire questo:

Change_weight(G) 
    for i = 1 to n 
    c_i = min(c_ij) for all j 
    if c_i < 0 
     c_ij = c_ij-c_i for all j 
     c_ki = c_ki+c_i for all k 

Cioè, per ogni vertice i, se il bordo in uscita più piccola c_i è negativo, quindi aumentare i pesi di tutti gli archi uscenti da -c_i e diminuire i pesi di tutti gli archi in arrivo -c_i. Poi il bordo in uscita più piccolo avrà peso pari a 0.

In secondo luogo, di per sé, questo algoritmo non garantisce che G' non ci sono spigoli negativi! consideri il seguente grafico:

Qui, il valore di bordo (1,2) viene spinto fino a 0 dall'operazione su 1, ma viene spinta indietro a -1 dall'operazione su 2. È necessario specificare che il grafico si trovi nell'ordine topologico inverso, in modo che il fronte (i,j) sia sempre operativo da j prima di essere utilizzato da i. (In alternativa, è possibile ordinarlo in ordine topologico e iterare da n to 1.)

---

risposta alla vostra domanda:

1) Il percorso più breve tra ogni due vertici in G è lo stesso che in G'.

Questo è vero. Considera un percorso non come una tupla di spigoli ma come una tupla di nodi. Per i vertici s e t, un percorso è una tupla di nodi (s, v_1, v_2, ..., t) in cui è presente un margine tra ogni due elementi successivi. Per ogni vertice u, u, il costo dei bordi in entrata è diminuito alla stessa velocità con cui è aumentato il costo dei bordi in uscita; pertanto, il costo relativo di includere u nel percorso è invariato.

2) Il peso del percorso più breve tra ogni due vertici inè lo stesso di G'.

Questo è falso. La sorgente s aumenta il peso in uscita di -c_s, mentre la destinazione t diminuisce il peso in entrata di -c_t. Se c_s != c_t, il peso del percorso non sarà lo stesso.

Per reiterare, il peso di ogni percorso da s a t verrà aumentato di (c_t-c_s). Pertanto, il percorso più breve per una data coppia s e t sarà ancora il più breve (poiché tutti i percorsi tra questa coppia cambiano della stessa quantità). Tuttavia, il peso ovviamente non sarà necessariamente lo stesso.