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