# Dijkstra Note
## 介紹dijkstraㄉ文章:
http://www.csie.ntnu.edu.tw/~u91029/Path.html
可以先讀一下喔 :pouting_cat:
---
## 以走迷宮圖的最短路徑為例 :hamster:
https://zerojudge.tw/ShowProblem?problemid=d793
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef struct Node {
int i;
int j;
int dis;
bool operator<(const Node& a) const {
return a.dis < dis;
}
} node;
int ta, N, M; // taskAmount
int maze[1000][1000];
int dis[1000][1000];
bool flag[1000][1000];
int mv[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
priority_queue<node> dispq;
void dijsktra() {
while (!dispq.empty()) {
flag[dispq.top().i][dispq.top().j] = true;
for (int k = 0; k < 4; k++) {
node nn; //nextNode
nn.i = dispq.top().i + mv[k][0];
nn.j = dispq.top().j + mv[k][1];
nn.dis = dis[nn.i][nn.j];
if ((nn.i < N && nn.i >= 0) && (nn.j < M && nn.j >= 0) && (!flag[nn.i][nn.j])) {
if (dispq.top().dis + maze[nn.i][nn.j] < nn.dis) {
nn.dis = dispq.top().dis + maze[nn.i][nn.j];
dispq.push(nn);
dis[nn.i][nn.j] = nn.dis;
}
}
}
dispq.pop();
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
cin >> ta;
while (ta--) {
//int p[1000][1000];
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> maze[i][j];
flag[i][j] = 0;
dis[i][j] = 9999999;
}
}
node n = {0, 0, maze[0][0]};
dis[0][0] = maze[0][0];
dispq.push(n);
dijsktra();
cout << dis[N - 1][M - 1] << '\n';
}
}
```
---
1.
| <span style="color:green"> 0 </span> | <span style="color:red"> 3 </span> | 1 | 2 | 9 |
|---|---|---|---|---|
| <span style="color:red"> 7 </span> | 3 | 4 | 9 | 9 |
| 1 | 7 | 5 | 5 | 3 |
| 2 | 3 | 4 | 2 | 5 |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:red"> 3 </span> | INF | INF | INF |
|---|---|---|---|---|
| <span style="color:red"> 7 </span> | INF | INF | INF | INF |
| INF | INF | INF | INF | INF |
| INF | INF | INF | INF | INF |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (0 , 1) ，距離： 3 :dog:
---
2.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:green"> 3 </span> | <span style="color:red"> 1 </span> | 2 | 9 |
|---|---|---|---|---|
| 7 | <span style="color:red"> 3 </span> | 4 | 9 | 9 |
| 1 | 7 | 5 | 5 | 3 |
| 2 | 3 | 4 | 2 | 5 |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:red"> 4 </span> | INF | INF |
|---|---|---|---|---|
| 7 | <span style="color:red"> 6 </span> | INF | INF | INF |
| INF | INF | INF | INF | INF |
| INF | INF | INF | INF | INF |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (0 , 2) ，距離： 4 :dog:
---
3.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:green"> 1 </span> | <span style="color:red"> 2 </span> | 9 |
|---|---|---|---|---|
| 7 | 3 | <span style="color:red"> 4 </span> | 9 | 9 |
| 1 | 7 | 5 | 5 | 3 |
| 2 | 3 | 4 | 2 | 5 |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:red"> 6 </span> | INF |
|---|---|---|---|---|
| 7 | 6 | <span style="color:red"> 8 </span> | INF | INF |
| INF | INF | INF | INF | INF |
| INF | INF | INF | INF | INF |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (1 , 1) ，距離： 6 :dog:
---
4.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~1~~ </span> | 2 | 9 |
|---|---|---|---|---|
| <span style="color:red"> 7 </span> | <span style="color:green"> 3 </span> | <span style="color:red"> 4 </span> | 9 | 9 |
| 1 | <span style="color:red"> 7 </span> | 5 | 5 | 3 |
| 2 | 3 | 4 | 2 | 5 |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | 6 | INF |
|---|---|---|---|---|
| <span style="color:red"> 7 </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:red"> 8 </span> | INF | INF |
| INF | <span style="color:red"> 13 </span> | INF | INF | INF |
| INF | INF | INF | INF | INF |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (0 , 3) ，距離： 6 :dog:
---
5.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~1~~ </span> | <span style="color:green"> 2 </span> | <span style="color:red"> 9 </span> |
|---|---|---|---|---|
| 7 | <span style="color:gray"> ~~3~~ </span> | 4 | <span style="color:red"> 9 </span> | 9 |
| 1 | 7 | 5 | 5 | 3 |
| 2 | 3 | 4 | 2 | 5 |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:red"> 15 </span> |
|---|---|---|---|---|
| 7 | <span style="color:gray"> ~~6~~ </span> | 8 | <span style="color:red"> 15 </span> | INF |
| INF | 13 | INF | INF | INF |
| INF | INF | INF | INF | INF |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (1 , 0) ，距離： 7 :dog:
---
6.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~2~~ </span> | 9 |
|---|---|---|---|---|
| <span style="color:green"> 7 </span> | <span style="color:gray"> ~~3~~ </span> | 4 | 9 | 9 |
| <span style="color:red"> 1 </span> | 7 | 5 | 5 | 3 |
| 2 | 3 | 4 | 2 | 5 |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~6~~ </span> | 15 |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~6~~ </span> | 8 | 15 | INF |
| <span style="color:red"> 8 </span> | 13 | INF | INF | INF |
| INF | INF | INF | INF | INF |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (2 , 0) ，距離： 8 :dog:
---
7.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~2~~ </span> | 9 |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~3~~ </span> | 4 | 9 | 9 |
| <span style="color:green"> 1 </span> | <span style="color:red"> 7 </span> | 5 | 5 | 3 |
| <span style="color:red"> 2 </span> | 3 | 4 | 2 | 5 |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~6~~ </span> | 15 |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~6~~ </span> | 8 | 15 | INF |
| <span style="color:gray"> ~~8~~ </span> | <span style="color:red"> 13 </span> | INF | INF | INF |
| <span style="color:red"> 10 </span> | INF | INF | INF | INF |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (1 , 2) ，距離： 8 :dog:
---
8.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~2~~ </span> | 9 |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:green"> 4 </span> | <span style="color:red"> 9 </span> | 9 |
| <span style="color:gray"> ~~1~~ </span> | 7 | <span style="color:red"> 5 </span> | 5 | 3 |
| 2 | 3 | 4 | 2 | 5 |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~6~~ </span> | 15 |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~8~~ </span> | <span style="color:red"> 15 </span> | INF |
| <span style="color:gray"> ~~8~~ </span> | 13 | <span style="color:red"> 13 </span> | INF | INF |
| 10 | INF | INF | INF | INF |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (3 , 0) ，距離： 10 :dog:
---
9.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~2~~ </span> | 9 |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | 9 | 9 |
| <span style="color:gray"> ~~1~~ </span> | 7 | 5 | 5 | 3 |
| <span style="color:green"> 2 </span> | <span style="color:red"> 3 </span> | 4 | 2 | 5 |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~6~~ </span> | 15 |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~8~~ </span> | 15 | INF |
| <span style="color:gray"> ~~8~~ </span> | 13 | 13 | INF | INF |
| <span style="color:gray"> ~~10~~ </span> | <span style="color:red"> 13 </span> | INF | INF | INF |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (2 , 2) ，距離： 13 :dog:
---
10.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~2~~ </span> | 9 |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | 9 | 9 |
| <span style="color:gray"> ~~1~~ </span> | <span style="color:red"> 7 </span> | <span style="color:green"> 5 </span> | <span style="color:red"> 5 </span> | 3 |
| <span style="color:gray"> ~~2~~ </span> | 3 | <span style="color:red"> 4 </span> | 2 | 5 |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~6~~ </span> | 15 |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~8~~ </span> | 15 | INF |
| <span style="color:gray"> ~~8~~ </span> | <span style="color:red"> 13 </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:red"> 18 </span> | INF |
| <span style="color:gray"> ~~10~~ </span> | 13 | <span style="color:red"> 17 </span> | INF | INF |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (3 , 1) ，距離： 13 :dog:
---
11.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~2~~ </span> | 9 |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | 9 | 9 |
| <span style="color:gray"> ~~1~~ </span> | <span style="color:red"> 7 </span> | <span style="color:gray"> ~~5~~ </span> | 5 | 3 |
| <span style="color:gray"> ~~2~~ </span> | <span style="color:green"> 3 </span> | <span style="color:red"> 4 </span> | 2 | 5 |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~6~~ </span> | 15 |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~8~~ </span> | 15 | INF |
| <span style="color:gray"> ~~8~~ </span> | <span style="color:red"> 13 </span> | <span style="color:gray"> ~~13~~ </span> | 18 | INF |
| <span style="color:gray"> ~~10~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:red"> 17 </span> | INF | INF |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (2 , 1) ，距離： 13 :dog:
---
12.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~2~~ </span> | 9 |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | 9 | 9 |
| <span style="color:gray"> ~~1~~ </span> | <span style="color:green"> 7 </span> | <span style="color:gray"> ~~5~~ </span> | 5 | 3 |
| <span style="color:gray"> ~~2~~ </span> | <span style="color:gray"> ~~3~~ </span> | 4 | 2 | 5 |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~6~~ </span> | 15 |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~8~~ </span> | 15 | INF |
| <span style="color:gray"> ~~8~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~13~~ </span> | 18 | INF |
| <span style="color:gray"> ~~10~~ </span> | <span style="color:gray"> ~~13~~ </span> | 17 | INF | INF |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (1 , 3) ，距離： 15 :dog:
---
13.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~2~~ </span> | 9 |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:green"> 9 </span> | <span style="color:red"> 9 </span> |
| <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~5~~ </span> | <span style="color:red"> 5 </span> | 3 |
| <span style="color:gray"> ~~2~~ </span> | <span style="color:gray"> ~~3~~ </span> | 4 | 2 | 5 |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~6~~ </span> | 15 |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~8~~ </span> | <span style="color:gray"> ~~15~~ </span> | <span style="color:red"> 24 </span> |
| <span style="color:gray"> ~~8~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:red"> 18 </span> | INF |
| <span style="color:gray"> ~~10~~ </span> | <span style="color:gray"> ~~13~~ </span> | 17 | INF | INF |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (0 , 4) ，距離： 15 :dog:
---
14.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~2~~ </span> | <span style="color:green"> 9 </span> |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~9~~ </span> | <span style="color:red"> 9 </span> |
| <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~5~~ </span> | 5 | 3 |
| <span style="color:gray"> ~~2~~ </span> | <span style="color:gray"> ~~3~~ </span> | 4 | 2 | 5 |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~15~~ </span> |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~8~~ </span> | <span style="color:gray"> ~~15~~ </span> | <span style="color:red"> 24 </span> |
| <span style="color:gray"> ~~8~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~13~~ </span> | 18 | INF |
| <span style="color:gray"> ~~10~~ </span> | <span style="color:gray"> ~~13~~ </span> | 17 | INF | INF |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (3 , 2) ，距離： 17 :dog:
---
15.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~2~~ </span> | <span style="color:gray"> ~~9~~ </span> |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~9~~ </span> | 9 |
| <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~5~~ </span> | 5 | 3 |
| <span style="color:gray"> ~~2~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:green"> 4 </span> | <span style="color:red"> 2 </span> | 5 |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~15~~ </span> |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~8~~ </span> | <span style="color:gray"> ~~15~~ </span> | 24 |
| <span style="color:gray"> ~~8~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~13~~ </span> | 18 | INF |
| <span style="color:gray"> ~~10~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~17~~ </span> | <span style="color:red"> 19 </span> | INF |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (2 , 3) ，距離： 18 :dog:
---
16.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~2~~ </span> | <span style="color:gray"> ~~9~~ </span> |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~9~~ </span> | 9 |
| <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~5~~ </span> | <span style="color:green"> 5 </span> | <span style="color:red"> 3 </span> |
| <span style="color:gray"> ~~2~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:red"> 2 </span> | 5 |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~15~~ </span> |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~8~~ </span> | <span style="color:gray"> ~~15~~ </span> | 24 |
| <span style="color:gray"> ~~8~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~18~~ </span> | <span style="color:red"> 21 </span> |
| <span style="color:gray"> ~~10~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~17~~ </span> | <span style="color:red"> 19 </span> | INF |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (3 , 3) ，距離： 19 :dog:
---
17.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~2~~ </span> | <span style="color:gray"> ~~9~~ </span> |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~9~~ </span> | 9 |
| <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~5~~ </span> | <span style="color:gray"> ~~5~~ </span> | 3 |
| <span style="color:gray"> ~~2~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:green"> 2 </span> | <span style="color:red"> 5 </span> |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~15~~ </span> |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~8~~ </span> | <span style="color:gray"> ~~15~~ </span> | 24 |
| <span style="color:gray"> ~~8~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~18~~ </span> | 21 |
| <span style="color:gray"> ~~10~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~17~~ </span> | <span style="color:gray"> ~~19~~ </span> | <span style="color:red"> 24 </span> |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (2 , 4) ，距離： 21 :dog:
---
18.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~2~~ </span> | <span style="color:gray"> ~~9~~ </span> |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~9~~ </span> | <span style="color:red"> 9 </span> |
| <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~5~~ </span> | <span style="color:gray"> ~~5~~ </span> | <span style="color:green"> 3 </span> |
| <span style="color:gray"> ~~2~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~2~~ </span> | <span style="color:red"> 5 </span> |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~15~~ </span> |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~8~~ </span> | <span style="color:gray"> ~~15~~ </span> | <span style="color:red"> 24 </span> |
| <span style="color:gray"> ~~8~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~18~~ </span> | <span style="color:gray"> ~~21~~ </span> |
| <span style="color:gray"> ~~10~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~17~~ </span> | <span style="color:gray"> ~~19~~ </span> | <span style="color:red"> 24 </span> |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (3 , 4) ，距離： 24 :dog:
---
19.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~2~~ </span> | <span style="color:gray"> ~~9~~ </span> |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~9~~ </span> | 9 |
| <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~5~~ </span> | <span style="color:gray"> ~~5~~ </span> | <span style="color:gray"> ~~3~~ </span> |
| <span style="color:gray"> ~~2~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~2~~ </span> | <span style="color:green"> 5 </span> |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~15~~ </span> |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~8~~ </span> | <span style="color:gray"> ~~15~~ </span> | 24 |
| <span style="color:gray"> ~~8~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~18~~ </span> | <span style="color:gray"> ~~21~~ </span> |
| <span style="color:gray"> ~~10~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~17~~ </span> | <span style="color:gray"> ~~19~~ </span> | <span style="color:gray"> ~~24~~ </span> |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (1 , 4) ，距離： 24 :dog:
---
20.
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~2~~ </span> | <span style="color:gray"> ~~9~~ </span> |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~9~~ </span> | <span style="color:green"> 9 </span> |
| <span style="color:gray"> ~~1~~ </span> | <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~5~~ </span> | <span style="color:gray"> ~~5~~ </span> | <span style="color:gray"> ~~3~~ </span> |
| <span style="color:gray"> ~~2~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~2~~ </span> | <span style="color:gray"> ~~5~~ </span> |
| <span style="color:gray"> ~~0~~ </span> | <span style="color:gray"> ~~3~~ </span> | <span style="color:gray"> ~~4~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~15~~ </span> |
|---|---|---|---|---|
| <span style="color:gray"> ~~7~~ </span> | <span style="color:gray"> ~~6~~ </span> | <span style="color:gray"> ~~8~~ </span> | <span style="color:gray"> ~~15~~ </span> | <span style="color:gray"> ~~24~~ </span> |
| <span style="color:gray"> ~~8~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~18~~ </span> | <span style="color:gray"> ~~21~~ </span> |
| <span style="color:gray"> ~~10~~ </span> | <span style="color:gray"> ~~13~~ </span> | <span style="color:gray"> ~~17~~ </span> | <span style="color:gray"> ~~19~~ </span> | <span style="color:gray"> ~~24~~ </span> |
透過<span style="color:green">綠色</span>這格更新旁邊的<span style="color:red">紅色</span>格ㄉ最短路徑，再從**所有格子**中挑選**未走過**且路徑**最短**者繼續尋找 ，即格子： (1 , 4) ，距離： 24 :dog:
---
{"metaMigratedAt":"2023-06-15T06:17:06.472Z","metaMigratedFrom":"Content","title":"Dijkstra Note","breaks":true,"contributors":"[{\"id\":\"5f9f7e4d-9793-42f6-a57f-44eaaa88ef69\",\"add\":167017,\"del\":138559}]"}