Percorsi minimi come soluzione di un programma lineare di uno speciale flusso di rete

Question

Permettere $ G = (v, e) $ essere un dato grafico ponderato diretto e $ s, t $ Due nodi specificati, in modo che non vi sia alcun ciclo negativo raggiungibile da $ s $, e $ t $ è raggiungibile da $ s $.
Stiamo cercando il percorso più breve.

Per quanto riguarda questo problema come una rete di flusso speciale, possiamo esprimerlo usando la programmazione lineare come segue:

Ridurre al minimo la funzione:$$ sum_ {e in e} c_e CDOT X_E $$

Sotto i vincoli:$$ forall v in v - {s, t }: sum_ {e in in (v)} x_e - sum_ {e in out (v)} x_e = 0 sum_ {e in out (s)} x_e = 1 sum_ {e in in (t)} x_e = 1 sum_ {e in in (s)} x_e = 0 sum_ {e in out (t)} x_e = 0 forall e in e: x_e ge 0 $$

Qui $ c_e $ sono i pesi dei bordi, $ in (v) $ sono tutti i bordi che entrano in $ V $, e $ out (v) $ sono tutti bordi a partire da $ V $.

Sulla correttezza:

Permettere $ S $ Sii una soluzione al programma lineare sopra. Poiché i vincoli sono gli stessi dei flussi di rete (se vediamo ogni bordo con una capacità infinita), $ S $ è un flusso $ G $.

Dato che ogni $ st $-Path soddisfa i vincoli, possiamo concludere che se $ S $ è un $ st $-PPATH, allora è un $ st $-Path con costi minimi.

Ulteriore, $ S $ Non posso contenere alcun ciclo con peso positivo, poiché potremmo semplicemente rimuovere questo ciclo $ S $ e finire con una soluzione a basso costo che soddisfa i vincoli.

Infine, $ S $ deve essere un $ st $-sentiero. Assumiamo $ S $ non lo era. Dato che $ S $ è un flusso, sappiamo che deve contenere alcuni $ st $-sentiero. Quindi lascia $ M $ essere il set di tutti $ st $-Paths That $ S $ contiene.
Quindi c'è un percorso con costi minimi in $ M $ (come $ S $ è privo di ciclo e quindi possono esserci solo molti elementi $ M $). Lascialo $ st $-PPATH BE $ p_ {min} $.

Se lo permettiamo $ c: m a mathbb r $ ora sii la mappa che assegna ciascuno $ st $-Path in $ M $ Il suo costo, abbiamo obtiano la seguente disuguaglianza:$$ 1 CDOT P_ {min} le sum_ {p in m} lambda_p CDOT P qquad text {dato che} forall p in m: lambda_p ge 0, sum_ {p in M} lambda_p = 1 $$

Pertanto, se $ S $ Conterrebbe più $ st $-Paths, non sarebbe minimo.

Quindi possiamo concludere, quello $ S $ è minimo $ st $-sentiero.

La mia domanda ora è: mi sono perso qualcosa nella prova?

---

Addendum:

Si scopre che la prova di cui sopra necessita di ciascuno $ st $-Path ha un costo unico. Altrimenti, potrebbe non esserci un singolo $ st $-Path con costi minimi. In questo caso, non si può dimostrare che la soluzione $ S $ Contiene solo un singolo di questi percorsi con costi minimi.
Tuttavia, in questo caso, dal ragionamento sopra, è ancora vero che ogni percorso in $ S $ è ottimale. Quindi in questo caso, possiamo semplicemente scegliere qualsiasi percorso $ S $ come soluzione (che possiamo trovare usando EG DFS)

Alcune osservazioni finali (fuori tema):
L'intera procedura sembra molto per un metodo meno efficiente per ottenere un percorso più breve. Ciò che ha attirato la mia attenzione sono state le seguenti due proprietà di questo algoritmo:
$ (i) $ Oltre al vincolo di non negatività, tutti i vincoli sono in realtà uguaglianze.
$ (ii) $ L'algoritmo dovrebbe essere facilmente adattabile per consentire anche cicli negativi (ponendo una certa restrizione lineare sulla soluzione, ad esempio che il percorso non deve essere troppo lungo, ecc.)