> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/path-related/dijkstras-algo.md).

# Dijkstra's Algo

{% embed url="<https://www.youtube.com/watch?v=FSm1zybd0Tk&t=15s>" %}

![](https://s3.us-west-2.amazonaws.com/secure.notion-static.com/f0f47a6f-a75e-40f3-b70a-2099887f16ee/Untitled.png?X-Amz-Algorithm=AWS4-HMAC-SHA256\&X-Amz-Credential=AKIAT73L2G45O3KS52Y5%2F20210703%2Fus-west-2%2Fs3%2Faws4_request\&X-Amz-Date=20210703T142609Z\&X-Amz-Expires=86400\&X-Amz-Signature=65852323b89fa2ac1f493d054b51d481fbafd24a02745ca832dae334b53dfcd1\&X-Amz-SignedHeaders=host\&response-content-disposition=filename%20%3D%22Untitled.png%22)

![](https://s3.us-west-2.amazonaws.com/secure.notion-static.com/7164aabf-0873-4895-b27c-e21a405cd825/Untitled.png?X-Amz-Algorithm=AWS4-HMAC-SHA256\&X-Amz-Credential=AKIAT73L2G45O3KS52Y5%2F20210703%2Fus-west-2%2Fs3%2Faws4_request\&X-Amz-Date=20210703T142700Z\&X-Amz-Expires=86400\&X-Amz-Signature=6de0e05644ea3660ed8d1ea0b2a401bfbf2d8cd525ab8fd991c44b4ce960fea6\&X-Amz-SignedHeaders=host\&response-content-disposition=filename%20%3D%22Untitled.png%22)

即使中間多了一個 Ａ 2.5, 0.4 在下一輪仍然可以 update 成2.9

![](https://s3.us-west-2.amazonaws.com/secure.notion-static.com/5741c967-0ac4-4e4f-85f6-0ac3e908a229/Untitled.png?X-Amz-Algorithm=AWS4-HMAC-SHA256\&X-Amz-Credential=AKIAT73L2G45O3KS52Y5%2F20210703%2Fus-west-2%2Fs3%2Faws4_request\&X-Amz-Date=20210703T142717Z\&X-Amz-Expires=86400\&X-Amz-Signature=0fac064c41e00269fb46aeb70572540b5b1058954df324fe7dd508b4b64369bc\&X-Amz-SignedHeaders=host\&response-content-disposition=filename%20%3D%22Untitled.png%22)

但如果是更差的結果, seattle: 3 不需要更新

![](https://s3.us-west-2.amazonaws.com/secure.notion-static.com/da8dba2b-730e-44d7-bec3-142c6530a899/Untitled.png?X-Amz-Algorithm=AWS4-HMAC-SHA256\&X-Amz-Credential=AKIAT73L2G45O3KS52Y5%2F20210703%2Fus-west-2%2Fs3%2Faws4_request\&X-Amz-Date=20210703T142742Z\&X-Amz-Expires=86400\&X-Amz-Signature=11fd26f0d3656fd02833e813a4732d9b96d9586263758bd04dbb336a24ddbee6\&X-Amz-SignedHeaders=host\&response-content-disposition=filename%20%3D%22Untitled.png%22)

## Solution - Dijkstra for 1631

1. create an effort matrix stores effort record
2. create PriorityQueue accept int\[] : new\_dist(effort), row, col, order by effort (minHeap)
3. while PriorityQueue is not empty
   1. poll node data from PriorityQueue (the smallest dist and row, col index)
   2. if dist > effort\[row]\[col] ⇒ skip this round
   3. if row & col == last cell ⇒ return result
   4. search this node's all neighbors, find new dist ⇒ new smaller effort
   5. if find new dist < effort\[new\_row]\[new\_col] ⇒ update effort\[new\_row]\[new\_col] = new dist, and offer new smaller dist into PriorityQueue

<https://www.youtube.com/watch?v=FabSLaGu0NI>