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