Rethink the Dijkstra algorithm -- Let's go deeper

Revision en15, by CristianoPenaldo, 2022-10-10 08:38:13

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}\}$$$.

However, dij works for a function class, not only the sum/max functions. The sum/max functions are only the two most frequently used members of this function class, but the function class is far larger than these two. Once the function $$$f$$$ satisfies several mandatory properties, you could use dij. The word "function class" is like an interface in Go/Java and an abstract class in C++:

struct f{
    virtual void property1() = 0;
    virtual void property2() = 0;
    virtual void property3() = 0;
    //...
};//dijkstra function.
dij(f);

For dij there has to be a non-empty source set $$$S$$$. The $$$S$$$ needs not to be a singleton, e.g., multi-source dij. 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}$$$. To be brief, $$$f(\{v_1, v_2, ..., v_n\})$$$ is shorten to $$$f(v_1, v_2, ..., v_n)$$$. $$$f$$$ has to satisfy three properties:

(1, induction base) $$$\forall s \in S$$$, $$$f(s)$$$ should be correctly initialized.

(2, Extension property) $$$\forall p$$$, for every vertex $$$v$$$ adjacent to the end of $$$p$$$ (p.back()), $$$f(p \cup v) \geq f(p)$$$.

(3, dynamic programming) If path $$$p, q$$$ has the same end (i.e., p.back()==q.back()) and $$$f(p) \geq f(q)$$$, then for every vertex $$$v$$$ adjacent to p.back(), $$$f(p \cup v) \geq f(q \cup v)$$$.

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)