Rethink the Dijkstra algorithm -- Let's go deeper

Revision en8, by CristianoPenaldo, 2022-10-10 08:02:43

This is a blog for cp newbies (like me).

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 $$$min \{f(p)|p\,\text{is a s-t path}\}$$$.

I want to say that dij works for a function class, not only the sum/max functions. Once the function $$$f$$$ satisfies several mandatory properties, you could use dij. You could view more formal statements in the paragraphs below.

A path $$$p$$$ is a vector of vertices $$$\{v_1, v_2, ..., v_n\}$$$ and the function $$$f$$$ is a function that maps paths to real numbers: $$$\text{path} \rightarrow \mathbb{R}$$$.

Tags dijkstra, graph theory, functional programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en77 English CristianoPenaldo 2022-10-10 16:15:01 19
en76 English CristianoPenaldo 2022-10-10 15:20:42 6
en75 English CristianoPenaldo 2022-10-10 15:13:56 2
en74 English CristianoPenaldo 2022-10-10 15:09:57 110 (published)
en73 English CristianoPenaldo 2022-10-10 15:08:00 31 (saved to drafts)
en72 English CristianoPenaldo 2022-10-10 13:37:13 2
en71 English CristianoPenaldo 2022-10-10 13:34:11 3
en70 English CristianoPenaldo 2022-10-10 13:32:43 0 (published)
en69 English CristianoPenaldo 2022-10-10 13:32:19 36 (saved to drafts)
en68 English CristianoPenaldo 2022-10-10 13:31:17 530 (published)
en67 English CristianoPenaldo 2022-10-10 13:25:58 127
en66 English CristianoPenaldo 2022-10-10 13:24:03 172
en65 English CristianoPenaldo 2022-10-10 13:14:11 426
en64 English CristianoPenaldo 2022-10-10 13:09:47 138
en63 English CristianoPenaldo 2022-10-10 13:06:14 92
en62 English CristianoPenaldo 2022-10-10 13:05:30 82
en61 English CristianoPenaldo 2022-10-10 12:47:38 207
en60 English CristianoPenaldo 2022-10-10 12:42:59 566
en59 English CristianoPenaldo 2022-10-10 12:28:21 807
en58 English CristianoPenaldo 2022-10-10 12:26:11 43
en57 English CristianoPenaldo 2022-10-10 12:24:29 12 Tiny change: 'nature of operator$+$, it satis' -> 'nature of add, it satis'
en56 English CristianoPenaldo 2022-10-10 12:24:00 339
en55 English CristianoPenaldo 2022-10-10 12:20:57 58
en54 English CristianoPenaldo 2022-10-10 12:16:51 2 Tiny change: 'g order:\n- 6, 4, 4, 2' -> 'g order:\n6, 4, 4, 2'
en53 English CristianoPenaldo 2022-10-10 12:12:54 142
en52 English CristianoPenaldo 2022-10-10 12:11:43 105
en51 English CristianoPenaldo 2022-10-10 12:09:29 106
en50 English CristianoPenaldo 2022-10-10 12:08:00 98
en49 English CristianoPenaldo 2022-10-10 12:04:51 58
en48 English CristianoPenaldo 2022-10-10 12:02:01 390
en47 English CristianoPenaldo 2022-10-10 11:51:36 341
en46 English CristianoPenaldo 2022-10-10 11:35:49 594
en45 English CristianoPenaldo 2022-10-10 11:24:49 4 Tiny change: '], k = 5\nOutput: 2\nExplanat' -> '], k = 5\n\nOutput: 2\n\nExplanat'
en44 English CristianoPenaldo 2022-10-10 11:24:13 636
en43 English CristianoPenaldo 2022-10-10 11:11:57 785
en42 English CristianoPenaldo 2022-10-10 10:55:25 65
en41 English CristianoPenaldo 2022-10-10 10:53:30 393
en40 English CristianoPenaldo 2022-10-10 10:40:51 1009
en39 English CristianoPenaldo 2022-10-10 10:32:56 467
en38 English CristianoPenaldo 2022-10-10 10:09:51 457
en37 English CristianoPenaldo 2022-10-10 10:03:10 172
en36 English CristianoPenaldo 2022-10-10 10:00:37 244
en35 English CristianoPenaldo 2022-10-10 09:43:49 554
en34 English CristianoPenaldo 2022-10-10 09:41:27 75
en33 English CristianoPenaldo 2022-10-10 09:35:29 148
en32 English CristianoPenaldo 2022-10-10 09:32:55 199
en31 English CristianoPenaldo 2022-10-10 09:30:42 233
en30 English CristianoPenaldo 2022-10-10 09:28:01 354
en29 English CristianoPenaldo 2022-10-10 09:25:05 231
en28 English CristianoPenaldo 2022-10-10 09:19:41 359
en27 English CristianoPenaldo 2022-10-10 09:09:04 183
en26 English CristianoPenaldo 2022-10-10 09:06:18 171
en25 English CristianoPenaldo 2022-10-10 09:02:53 62
en24 English CristianoPenaldo 2022-10-10 09:00:04 93
en23 English CristianoPenaldo 2022-10-10 08:58:11 5
en22 English CristianoPenaldo 2022-10-10 08:57:48 25
en21 English CristianoPenaldo 2022-10-10 08:56:55 42
en20 English CristianoPenaldo 2022-10-10 08:55:49 78
en19 English CristianoPenaldo 2022-10-10 08:55:04 37
en18 English CristianoPenaldo 2022-10-10 08:53:59 223
en17 English CristianoPenaldo 2022-10-10 08:51:11 514
en16 English CristianoPenaldo 2022-10-10 08:41:54 179
en15 English CristianoPenaldo 2022-10-10 08:38:13 212
en14 English CristianoPenaldo 2022-10-10 08:35:32 142
en13 English 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 English CristianoPenaldo 2022-10-10 08:18:55 165
en11 English CristianoPenaldo 2022-10-10 08:14:54 208
en10 English CristianoPenaldo 2022-10-10 08:11:52 514
en9 English CristianoPenaldo 2022-10-10 08:04:15 82
en8 English CristianoPenaldo 2022-10-10 08:02:43 66
en7 English CristianoPenaldo 2022-10-10 08:01:19 380
en6 English CristianoPenaldo 2022-10-10 07:56:08 3 Tiny change: ' \\{f(p)|p \text{is a' -> ' \\{f(p)|p\,\text{is a'
en5 English 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 English CristianoPenaldo 2022-10-10 07:55:32 1 Tiny change: 's-t\,paths}\\}$\n' -> 's-t\,paths\\}$\n'
en3 English 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 English 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 English CristianoPenaldo 2022-10-10 06:49:27 243 Initial revision (saved to drafts)