Rethink the Dijkstra algorithm -- Let's go deeper

→ Pay attention

Before contest
Codeforces Round 986 (Div. 2)
10:25:03
Register now »

*has extra registration

→ Streams

Codeforces Round 986 (Div 2) - Solution Discussion

By Shayan

Before stream 12:30:02

View all →

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

View all →

→ Find user

→ Recent actions

Detailed →

Rethink the Dijkstra algorithm -- Let's go deeper

Revision en2, by CristianoPenaldo, 2022-10-10 07:54:52

For a long time I think the Dijkstra algorithm (dij) only has two usages:

(1) Calculate the distance between the vertices when the weights of edges are non-negative.

(2) (Minimax) Given a path $$$p = x_1x_2...x_n$$$, define $$$f(p) := \max_{i=1}^{n-1}d(x_i, x_{i+1})$$$. Given source vertex $$$s$$$ and target vertex $$$t$$$, dij is able to calculate

Unable to parse markup [type=CF_MATHJAX]

\text {is a s-t path}\}$

dijkstra, graph theory, functional programming

History

Revisions

Rev.	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)