1
$\begingroup$

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 "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?

$\endgroup$
9
  • $\begingroup$ Since the weights are distinct, ties can not happen, right? $\endgroup$ – Inuyasha Yagami Jan 24 at 13:28
  • $\begingroup$ In that case, your first statement implies that the path found would be topologically minimum among all the paths. $\endgroup$ – Inuyasha Yagami Jan 24 at 13:28
  • $\begingroup$ I meant tied in the sense of maximum edge cost. For instance, if two paths have costs $\{5,3,2\}$ and $\{5,4,1\}$ (with both including the same cost-5 edge) then the first one will be found even though both are minimax paths. $\endgroup$ – Sneftel Jan 24 at 13:31
  • $\begingroup$ .... and when I said “topographical minimum” I should’ve said “lexicographic minimum”. Oops. $\endgroup$ – Sneftel Jan 24 at 13:36
  • 1
    $\begingroup$ Wouldn't that become Prim's algorithm, for minimal spanning tree? $\endgroup$ – Hendrik Jan Jan 24 at 13:39
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I’m specifically considering the case where edge costs are distinct, though. If the cost of $(v_1, v_3)$ is perturbed to be greater than 5 then it won’t be traversed until after $v_3$ is visited from $v_2$. And if it’s perturbed to be less than 5, then the resultant path is the only minimax path. Is there a counterexample which has distinct edge costs? $\endgroup$ – Sneftel Jan 24 at 13:19
  • $\begingroup$ @Sneftel I have updated the answer. Please check if it is valid. $\endgroup$ – Inuyasha Yagami Jan 25 at 15:09
  • $\begingroup$ Yep, that does seem to hold together. Thanks! $\endgroup$ – Sneftel Jan 25 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.