Comment by 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.