# Algorithm to find shortest distance from source to all other vertices of graph in O(m)?

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

• Do you have constant-time access to the vertex at coordinates $(i,j)$ given $i$ and $j$? Nov 23 at 16:12
• @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. Nov 23 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.