Kürzeste-Wege-Probleme lassen sich als Lineares Programm formulieren. Definiert wird:
ist der gerichtete, gewichtete Graph ist der Startknoten ist der Zielknoten sind die Kosten für jede Kante in ist die Entscheidungsvariable, die anzeigt, ob die Kante Teil des kürzesten Weges ist
Betrachtet wird nun das folgende LP:
Unter den Nebenbedingungen:
- Genau eine Kante verlässt
- Genau eine Kante endet in
- Keine Kante endet in
- Keine Kante verlässt
- Flusserhaltung: Genau so viele Verbindungen führen in den Knoten
hinein als auch wieder heraus. Wenn also eine Kante in hereinführt, dann führt auch eine (andere) wieder aus heraus. Der Weg endet nicht in - Binäreinschränkung für
Kompakte Schreibweise
Da Kreise in einem Optimum nicht vorkommen, ist es ausreichend, folgende Nebenbedingungen zu aufzustellen:
(Die Binäreinschränkung gilt weiterhin:)