Consider a variant of Dijkstra’s algorithm (for a directed graph) where nodes are visited not in order of total path cost, but in order of incoming edge cost. (Assume here that all edge costs are positive and distinct). Nodes are never re-visited. What can we say about the resultant paths?
One obvious result is that they are minimax paths (that is, the maximum edge cost of a path found is the minimum of that of any path to that goal). But the condition seems to be stronger than that: An edge pair will tend to have a large number of tied minimax paths (since only one edge really constrains the path), but this algorithm seems to robustly prefer paths with fewer high-cost edges.
What I think is going on is, the edge costs for the found path from
b, if sorted in descending order, produce a sequence that is the lexicographic minimum over all paths from
b. In a sense, it’s more “strongly” minimax, with ties broken by the second-highest-cost edge, and so on. But I can’t prove this to myself, even informally.
Is this a known algorithm? Does it actually have that property?