[arghbleargh]

There is a linear programming formulation of the shortest path problem: see https://en.m.wikipedia.org/wiki/Shortest_path_problem#Linear.... Indeed the vertices of the simplex method would correspond to paths, but I think running the simplex method on the dual formulation is more akin to Dijkstra's algorithm. Actually, I think the simplex method on the dual and Dijkstra's are equivalent, although I did not work through the details carefully.

[mathgenius]

Aha, yes, this is what I was looking for. Thankyou!

Reminds me also of using linear programming to do belief propagation and decode sparse codes.