> The reason the graph search doesn't turn into Dijkstra's algorithm is that we would never have any reason to backtrack. The next basis is always at least as good as the last, so we don't "get stuck" and we don't ask whether we would rather have gone another way earlier on.
I wonder if there is a sharper way of putting this.
Dijkstra's algorithm doesn't backtrack either, it is always merely propagating a "wave-front" of current best vertices (and perhaps how we got there). And the simplex method will also do this when presented with a connected component of vertices all of which have the same objective value.
I feel there are some deeper connections to "dynamic programming", of which Dijkstra's algorithm is a good example. Having trouble putting my finger on it.
One obvious difference is that the Simplex method doesn't know the target vertex, whereas we do know this in Dijkstra. So perhaps the (possibly non-existent) analogy I am searching for links vertices of the Simplex method with paths in Dijkstra.
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.
> best vertices (and perhaps how we got there). And the simplex method will also do this when presented with a connected component of vertices all of which have the same objective value.
It has been a while since I did implemented the simplex method, but I don't think this is accurate. There is only ever one basis stored. You don't need a collection of them to fix stalling/cycling.
> Dijkstra's algorithm doesn't backtrack either
I suppose this was a poor choice of language. The algorithm doesn't backtrack, but the whole point of the wavefront is to allow you to be noncommittal about which way you're going -- you explore many paths at once, something that would be very expensive to do on a simplex (where the big cost is the number of edges explored, not the number of edges on the shortest path.)
Edit: I guess you could see the simplex method as Astar with the heap key being just the heuristic (no "cost to this point" term.) Because of the structure of the graph, there's no need to keep the heap at all.
I wonder if there is a sharper way of putting this.
Dijkstra's algorithm doesn't backtrack either, it is always merely propagating a "wave-front" of current best vertices (and perhaps how we got there). And the simplex method will also do this when presented with a connected component of vertices all of which have the same objective value.
I feel there are some deeper connections to "dynamic programming", of which Dijkstra's algorithm is a good example. Having trouble putting my finger on it.
One obvious difference is that the Simplex method doesn't know the target vertex, whereas we do know this in Dijkstra. So perhaps the (possibly non-existent) analogy I am searching for links vertices of the Simplex method with paths in Dijkstra.