Rethink the Dijkstra algorithm -- Let's go deeper

Правка en14, от CristianoPenaldo, 2022-10-10 08:35:32

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$$$, that is neighbor to the last vertex of $$$p$$$ (p.back()), $$$f(p \cup v) \geq f(p)$$$.

Теги dijkstra, graph theory, functional programming

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)