Question is for (c)

My question is for (c), as I struggle to find an algorithm that can do this in O(m) time.

  • $\begingroup$ Do you have constant-time access to the vertex at coordinates $(i,j)$ given $i$ and $j$? $\endgroup$
    – Steven
    Nov 23 '21 at 16:12
  • $\begingroup$ @Warsick Don't use images as the main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. Please also give proper attribution to your sources. $\endgroup$ Nov 23 '21 at 16:13

Start at the bottom (at $s$). Traverse the bottom row back and forth in one loop, updating your Dijkstra label on each node. Then process each of the arcs that lead up to the next level, one at a time updating the labels of each node in that 2nd level. Then move up to the 2nd level and traverse that row back and forth as before, updating the label at each node. Continue. You traverse each arc at most once I think, so $O(m)$. This relies on the positive length of each arc obviously.

More formally, let $d(i)$=distance from $s$ to node $i$, for each node $i$. Let $c_{ij}$ be the cost of using arc $i$-->$j$. Start with $d(s)=0$ and $d(i)=+\infty$ for all other nodes. Starting in the bottom row, traverse each arc to the right starting at $s$. When you reach node $j$ from node $k$, do your update step: $d(j) = \min(d(j),d(k)+c_{kj})$. When you reach the right end, turn back and go back to $s$ (though you won't update anything on your way back in the bottom row this way). Now with the bottom row all updated, "process" the up arcs from the bottom row. So do the update step for each of the up arcs one by one (in any order). Then again traverse this row starting on the left, following each arc right until the end then back (applying the update step for each arc). Here you might update a label on your way back because there might be a really cheap arc that moves you from the bottom row to the 2nd row. Anyway, continue this until you traverse the top row.

  • $\begingroup$ Great suggestion, how would you argue for correctness of this algorithm? Is there a nice loop invariant that could be used, as in the proof for correctness of Dijkstra's algorithm, or do you have a more simple argument? $\endgroup$
    – Warsick
    Nov 25 '21 at 15:51
  • $\begingroup$ I think a proof could be constructed very much like the proof of Dijkstra (say here en.wikipedia.org/wiki/Dijkstra%27s_algorithm). $\endgroup$
    – TickaJules
    Nov 28 '21 at 1:13
  • $\begingroup$ My initial thought too - thanks. $\endgroup$
    – Warsick
    Nov 28 '21 at 18:43

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.