Chemins minimaux comme solution d'un programme linéaire d'un flux de réseau spécial

Question

Laisser $ G = (v, e) $ être un graphique pondéré dirigé donné, et $ s, t $ deux nœuds spécifiés, de sorte qu'il n'y a pas de cycle négatif accessible à partir de $ s $, et $ t $ est accessible de $ s $.
Nous recherchons le plus court stat.

En ce qui concerne ce problème comme un réseau de flux spécial, nous pouvons l'exprimer en utilisant la programmation linéaire comme suit:

Minimiser la fonction:$$ sum_ {e in e} c_e cdot x_e $$

Sous les contraintes:dollars in out (s)} x_e = 1 sum_ {e in in (t)} x_e = 1 sum_ {e in (s)} x_e = 0 sum_ {e in out (t)} x_e = 0 forall e in e: x_e ge 0 $$

Ici $ c_e $ sont les poids des bords, $ in (v) $ tous les arêtes sont-elles entrées $ v $, et $ out (v) $ Tous les bords commencent-ils $ v $.

À propos de l'exactitude:

Laisser $ S $ être une solution au programme linéaire ci-dessus. Comme les contraintes sont les mêmes que pour les flux de réseau (si nous voyons chaque bord comme ayant une capacité infinie), $ S $ est un flux sur $ G $.

Étant donné que chaque $ st $-Path remplit les contraintes, nous pouvons conclure que si $ S $ est un $ st $-Path, alors c'est un $ st $-Path avec des coûts minimaux.

Plus loin, $ S $ ne peut contenir aucun cycle avec un poids positif, car nous pouvions simplement supprimer ce cycle de $ S $ et se retrouvent avec une solution à moindre coût qui remplit les contraintes.

Pour terminer, $ S $ doit être un $ st $-chemin. Assumons $ S $ ce n'était pas. Étant donné que $ S $ est un flux, nous savons qu'il doit contenir certains $ st $-chemin. Alors laisse $ M $ être l'ensemble de tous $ st $-Paths que $ S $ contient.
Ensuite, il y a un chemin avec des coûts minimaux en $ M $ (comme $ S $ est sans cycle, et il ne peut donc y avoir que de nombreux éléments dans $ M $). Que ce soit $ st $-Path être $ p_ {min} $.

Si nous laissons $ c: m à mathbb r $ Soyez maintenant la carte qui attribue chacun $ st $-atter dans $ M $ son coût, nous obtons l'inégalité suivante:$$ 1 cdot p_ {min} le sum_ {p in m} lambda_p cdot p qquad text {étant donné que} forall p in m: lambda_p ge 0, sum_ {p in in M} lambda_p = 1 $$

Par conséquent, si $ S $ contiendrait plusieurs $ st $-Paths, ce ne serait pas minime.

Ainsi, nous pouvons conclure que $ S $ est un minimal $ st $-chemin.

Ma question est maintenant: ai-je manqué quelque chose dans la preuve?

---

Addenda:

Il s'avère que la preuve ci-dessus a besoin de chacun $ st $-Path a un coût unique. Sinon, il pourrait y avoir un seul $ st $-Path avec des coûts minimaux. Dans ce cas, on ne peut pas montrer que la solution $ S $ ne contient qu'un seul de ces chemins à coût minimal.
Cependant, dans ce cas, par le raisonnement ci-dessus, il est toujours vrai que chaque chemin dans $ S $ est optimal. Donc, dans ce cas, nous pouvons simplement choisir n'importe quel chemin $ S $ comme solution (que nous pouvons trouver en utilisant EG DFS)

Quelques remarques finales (hors sujet):
Toute cette procédure semble beaucoup pour une méthode moins efficace pour obtenir un chemin le plus court. Ce qui a attiré mon attention, ce sont les deux propriétés suivantes de cet algorithme:
$ (i) $ Outre la contrainte de non-négativité, toutes les contraintes sont en fait des égalités.
$ (ii) $ L'algorithme doit être facilement adaptable pour permettre également des cycles négatifs (en mettant une restriction linéaire sur la solution, par exemple que le chemin ne doit pas être trop long, etc.)