---- > [!theorem] Theorem. ([[Dijkstra's Algorithm]]) > **Dijkstra's Algorithm** is an [[algorithm]] for finding the shortest *weighted* path on a [[weighted network]] with $n$ nodes and $m$ edges. > \ > $\begin{align}&\text{Loop $n$ times}: \\ & \quad \text{Find unvisited node }v \text{ with the shortest distance} \\ & \quad \text{Mark }k _v \text{ as visited/true and remove it from the data structure} \\& \quad \text{For each adjacent unvisited node }u, \text{ do:} \\ & \quad \quad \text{ If }d_{v} + \text{weight}(v,u) < d_{u}: \\& \quad \quad \quad \text{Update }d_{u}\text{ to be that sum } p_{u} \text{ to be }v\end{align}$ \ **Remark.** Using a [[binary heap]] [[priority queue]] to keep track of distances, the [[time complexity]] of **Dijkstra's Algorithm** is $O\big( (m+n) \log n\big)$. This is because a [[priority queue]] implemented via a [[binary heap]] has $O(1)$ `top`, meaning that the second line is $O(1)$. The third line, `pop`ing $k_{v}$, is $O(\log n)$. After doing that, on average, there will be $O\left( \frac{m}{n} \right)$ adjacent nodes to check. Updating $d_{u}$ for these takes $O(\log n)$. So each iteration takes time $O\left( \frac{m}{n} \log n + \log n\right)$, and there are $n$ iterations. > [!basicexample] > Try walking through this on your own: > ![[CleanShot 2023-10-01 at [email protected]]] > (From EECS 281 lab 10) > [!proof]- Proof. ([[Dijkstra's Algorithm]]) > ~ ---- #### ----- #### References > [!backlink] > ```dataview TABLE rows.file.link as "Further Reading" FROM [[]] FLATTEN file.tags GROUP BY file.tags as Tag > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```