For a long time I think the Dijkstra only has two usages:
(1) Calculate the distance between the vertices when the weights of edges are non-negative.
(2) Given a path $$$p = x_1x_2...x_n$$$
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Rethink the Dijkstra algorithm -- Let's go deeper
For a long time I think the Dijkstra only has two usages:
(1) Calculate the distance between the vertices when the weights of edges are non-negative.
(2) Given a path $$$p = x_1x_2...x_n$$$
Rev. | Lang. | By | When | Δ | Comment | |
---|---|---|---|---|---|---|
en77 | CristianoPenaldo | 2022-10-10 16:15:01 | 19 | |||
en76 | CristianoPenaldo | 2022-10-10 15:20:42 | 6 | |||
en75 | CristianoPenaldo | 2022-10-10 15:13:56 | 2 | |||
en74 | CristianoPenaldo | 2022-10-10 15:09:57 | 110 | (published) | ||
en73 | CristianoPenaldo | 2022-10-10 15:08:00 | 31 | (saved to drafts) | ||
en72 | CristianoPenaldo | 2022-10-10 13:37:13 | 2 | |||
en71 | CristianoPenaldo | 2022-10-10 13:34:11 | 3 | |||
en70 | CristianoPenaldo | 2022-10-10 13:32:43 | 0 | (published) | ||
en69 | CristianoPenaldo | 2022-10-10 13:32:19 | 36 | (saved to drafts) | ||
en68 | CristianoPenaldo | 2022-10-10 13:31:17 | 530 | (published) | ||
en67 | CristianoPenaldo | 2022-10-10 13:25:58 | 127 | |||
en66 | CristianoPenaldo | 2022-10-10 13:24:03 | 172 | |||
en65 | CristianoPenaldo | 2022-10-10 13:14:11 | 426 | |||
en64 | CristianoPenaldo | 2022-10-10 13:09:47 | 138 | |||
en63 | CristianoPenaldo | 2022-10-10 13:06:14 | 92 | |||
en62 | CristianoPenaldo | 2022-10-10 13:05:30 | 82 | |||
en61 | CristianoPenaldo | 2022-10-10 12:47:38 | 207 | |||
en60 | CristianoPenaldo | 2022-10-10 12:42:59 | 566 | |||
en59 | CristianoPenaldo | 2022-10-10 12:28:21 | 807 | |||
en58 | CristianoPenaldo | 2022-10-10 12:26:11 | 43 | |||
en57 | CristianoPenaldo | 2022-10-10 12:24:29 | 12 | Tiny change: 'nature of operator$+$, it satis' -> 'nature of add, it satis' | ||
en56 | CristianoPenaldo | 2022-10-10 12:24:00 | 339 | |||
en55 | CristianoPenaldo | 2022-10-10 12:20:57 | 58 | |||
en54 | CristianoPenaldo | 2022-10-10 12:16:51 | 2 | Tiny change: 'g order:\n- 6, 4, 4, 2' -> 'g order:\n6, 4, 4, 2' | ||
en53 | CristianoPenaldo | 2022-10-10 12:12:54 | 142 | |||
en52 | CristianoPenaldo | 2022-10-10 12:11:43 | 105 | |||
en51 | CristianoPenaldo | 2022-10-10 12:09:29 | 106 | |||
en50 | CristianoPenaldo | 2022-10-10 12:08:00 | 98 | |||
en49 | CristianoPenaldo | 2022-10-10 12:04:51 | 58 | |||
en48 | CristianoPenaldo | 2022-10-10 12:02:01 | 390 | |||
en47 | CristianoPenaldo | 2022-10-10 11:51:36 | 341 | |||
en46 | CristianoPenaldo | 2022-10-10 11:35:49 | 594 | |||
en45 | CristianoPenaldo | 2022-10-10 11:24:49 | 4 | Tiny change: '], k = 5\nOutput: 2\nExplanat' -> '], k = 5\n\nOutput: 2\n\nExplanat' | ||
en44 | CristianoPenaldo | 2022-10-10 11:24:13 | 636 | |||
en43 | CristianoPenaldo | 2022-10-10 11:11:57 | 785 | |||
en42 | CristianoPenaldo | 2022-10-10 10:55:25 | 65 | |||
en41 | CristianoPenaldo | 2022-10-10 10:53:30 | 393 | |||
en40 | CristianoPenaldo | 2022-10-10 10:40:51 | 1009 | |||
en39 | CristianoPenaldo | 2022-10-10 10:32:56 | 467 | |||
en38 | CristianoPenaldo | 2022-10-10 10:09:51 | 457 | |||
en37 | CristianoPenaldo | 2022-10-10 10:03:10 | 172 | |||
en36 | CristianoPenaldo | 2022-10-10 10:00:37 | 244 | |||
en35 | CristianoPenaldo | 2022-10-10 09:43:49 | 554 | |||
en34 | CristianoPenaldo | 2022-10-10 09:41:27 | 75 | |||
en33 | CristianoPenaldo | 2022-10-10 09:35:29 | 148 | |||
en32 | CristianoPenaldo | 2022-10-10 09:32:55 | 199 | |||
en31 | CristianoPenaldo | 2022-10-10 09:30:42 | 233 | |||
en30 | CristianoPenaldo | 2022-10-10 09:28:01 | 354 | |||
en29 | CristianoPenaldo | 2022-10-10 09:25:05 | 231 | |||
en28 | CristianoPenaldo | 2022-10-10 09:19:41 | 359 | |||
en27 | CristianoPenaldo | 2022-10-10 09:09:04 | 183 | |||
en26 | CristianoPenaldo | 2022-10-10 09:06:18 | 171 | |||
en25 | CristianoPenaldo | 2022-10-10 09:02:53 | 62 | |||
en24 | CristianoPenaldo | 2022-10-10 09:00:04 | 93 | |||
en23 | CristianoPenaldo | 2022-10-10 08:58:11 | 5 | |||
en22 | CristianoPenaldo | 2022-10-10 08:57:48 | 25 | |||
en21 | CristianoPenaldo | 2022-10-10 08:56:55 | 42 | |||
en20 | CristianoPenaldo | 2022-10-10 08:55:49 | 78 | |||
en19 | CristianoPenaldo | 2022-10-10 08:55:04 | 37 | |||
en18 | CristianoPenaldo | 2022-10-10 08:53:59 | 223 | |||
en17 | CristianoPenaldo | 2022-10-10 08:51:11 | 514 | |||
en16 | CristianoPenaldo | 2022-10-10 08:41:54 | 179 | |||
en15 | CristianoPenaldo | 2022-10-10 08:38:13 | 212 | |||
en14 | CristianoPenaldo | 2022-10-10 08:35:32 | 142 | |||
en13 | CristianoPenaldo | 2022-10-10 08:19:16 | 31 | Tiny change: 'ion base) For **every** source point $s \in S$, ' -> 'ion base) $\forall s \in S$, ' | ||
en12 | CristianoPenaldo | 2022-10-10 08:18:55 | 165 | |||
en11 | CristianoPenaldo | 2022-10-10 08:14:54 | 208 | |||
en10 | CristianoPenaldo | 2022-10-10 08:11:52 | 514 | |||
en9 | CristianoPenaldo | 2022-10-10 08:04:15 | 82 | |||
en8 | CristianoPenaldo | 2022-10-10 08:02:43 | 66 | |||
en7 | CristianoPenaldo | 2022-10-10 08:01:19 | 380 | |||
en6 | CristianoPenaldo | 2022-10-10 07:56:08 | 3 | Tiny change: ' \\{f(p)|p \text{is a' -> ' \\{f(p)|p\,\text{is a' | ||
en5 | CristianoPenaldo | 2022-10-10 07:55:58 | 14 | Tiny change: '\{f(p)|p \in s-t\,paths\\}$\n' -> '\{f(p)|p \text{is a s-t path}\\}$\n' | ||
en4 | CristianoPenaldo | 2022-10-10 07:55:32 | 1 | Tiny change: 's-t\,paths}\\}$\n' -> 's-t\,paths\\}$\n' | ||
en3 | CristianoPenaldo | 2022-10-10 07:55:20 | 16 | Tiny change: 'n \\{f(p)|$p$ \text {is a s-t path}\\}$\n' -> 'n \\{f(p)|p \in s-t\,paths}\\}$\n' | ||
en2 | CristianoPenaldo | 2022-10-10 07:54:52 | 191 | Tiny change: 'p) := \min$\n' -> 'p) := \min_{i=1}^{n-1}d(x_i, x_{i+1})$\n' | ||
en1 | CristianoPenaldo | 2022-10-10 06:49:27 | 243 | Initial revision (saved to drafts) |
Name |
---|