What does Dijkstra's algorithm become, when you replace path cost with edge cost? 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 a to b, if sorted in descending order, produce a sequence that is the lexicographic minimum over all paths from a to b. In a sense, it's more &quot;strongly&quot; 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?
The following answer assumes that you know the working of Dijkstra's algorithm. Here, we are working with a variant of Dijkstra's algorithm as mentioned in the question. Hope it will be helpful.
Suppose $s$ is the source vertex and $v$ be any vertex in $V$.
Statement: Dijkstra's algorithm outputs the lexicographically smallest path from $s$ to $v$ if all the edge weights in the graph are positive and distinct.
Proof: Suppose $p = (s,u_{1},\dotsc,u_{q},v)$ is the lexicographically smallest path from $s$ to $v$. For the sake of contradiction, assume that the algorithm outputs $p' = (s,w_{1},\dotsc,w_{r},v)$ and $p' \neq p$. Let $(w_{i},w_{i+1})$ be an edge in $p'$ that act as a tie breaker when we compare the orderings of $p$ and $p'$. In other words, every edges in $p'$ that has the higher weight than the weight of $(w_{i},w_{i+1})$ does also appears in $p$. Let $E_{h}$ be the set of edges in $p'$ that have weight higher than the weight of $(w_{i},w_{i+1})$.

Claim: There is an edge $e$ in $p$ such that $e \notin E_{h}$ and $weight(e) &gt; weight(w_{i},w_{i+1})$.
Proof: I will assume that you are familiar with the fact that the algorithm maintains a cut $(S, V \setminus S)$ such that all the vertices in $S$ are declared visited and the shortest path to them has been found. Now, suppose that just before the algorithm adds $(w_{i},w_{i+1})$, the cut is $(S_{i}, V \setminus S_{i})$. It implies that for all $j \leq i$, $w_{j} \in S_{i}$ and for all $j &gt; i$, $w_{j} \in V \setminus S_{i}$. Also, $s \in S_{}$ and $v \in V \setminus S_{i}$. Now, consider path $p$. Since $p$ is a path from $s$ to $v$, there is an edge $e$ in $p$ that is also present in the cut $(S_{i}, V \setminus S_{i})$. Firstly, we will show that $e$ does not belongs to $p'$. For the sake of contradiction assume that $e$ also belongs to $p'$. Therefore, let us define $e$ to $(w_{t},w_{t+1}) \in p'$.
Case $1$:  $e$ appears before $(w_{i},w_{i+1})$ in the path sequence
$p'$. It means $w_{t}$ and $w_{t+1}$ belongs to $S_{i}$. It
contradicts that $(w_{t},w_{t+1})$ belongs to the cut $(S_{i},V \setminus S_{i})$.
Case $2$: $e$ appears after $(w_{i},w_{i+1})$ in the path sequence
$p'$. Let $(S_{t-1},V \setminus S_{t-1})$ be the cut just before
$(w_{t-1},w_{t})$ was added to the solution. We know that  $w_{t-1} \in S_{t-1}$ and also $w_{t} \in S_{i} \subset S_{t-1}$. Therefore, it
contradicts that $(w_{t-1},w_{t})$ belongs to the cut
$(S_{t-1},V\setminus S_{t-1})$.
From the above two cases, we can say that $e \notin p'$ and therefore $e \notin E_{h}$.
Also, note that the edges $e$ and $(w_{i},w_{i+1})$ both belongs to the cut $(S_{i},V \setminus S_{i})$, and the algorithm chooses $(w_{i},w_{i+1})$ over $e$. Therefore, the weight of $e$ is greater than the weight of $(w_{i},w_{i+1})$. This
proves the claim.

The above claim implies that $p'$ is lexicographically smaller than $p$. Therefore $p = p'$. It contradicts our initial assumtion that $p \neq p'$. Hence proved.