Rethink the Dijkstra algorithm -- Let's go deeper

Правка en39, от CristianoPenaldo, 2022-10-10 10:32:56

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 abstract class in C++:

struct f{
    virtual bool induction_property() = 0; //bool: satisfy or not
    virtual bool extension_property() = 0; //bool: satisfy or not
    virtual bool dp_property() = 0; //bool: satisfy or not
};//dijkstra function.
dij(f);

The graph $$$G=(V(G),E(G))$$$. WLOG we assume $$$G$$$ is connected. There is a non-empty source set $$$S \in V(G)$$$ that needs not be a singleton. 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: path→R. To be brief, $$$f(\{v_1,v_2,...,v_n\})$$$ is shorten to $$$f(v_1,v_2,...,v_n)$$$. We say that dij works for f if $$$\forall v \in V(G)$$$, dij correctly computes $$$d(v) := \min f(\{p \mid p\,\text{is a S-v path}\})$$$. f should satisfy three properties that are also sufficient:

(1, induction base) ∀s∈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 (dp) property) If path $$$p, q$$$ has the same end (i.e., p.back()==q.back()) and $$$f(p) > f(q)$$$, then for every vertex $$$v$$$ adjacent to p.back(), $$$f(p \cup v) > f(q \cup v)$$$.

The necessity of the induction base is obvious. Otherwise, the $$$f$$$(source vertices) are wrong. For the second property, it is well known that the sum version of dij (shortest path) does not work for edges with negative cost (but the max version works!). For the dp property, let's consider the following example:

In this example $$$f(p):=\sum\limits_{i=1}^{n-1} i \text{dis}(v_i, v_{i+1})$$$. $$$f(ABC) = 1+4*2 = 9$$$; $$$f(AC)=10$$$; $$$f(ABCD) = 1+4*2 + 5*3=24$$$, $$$f(ACD)=10+5*2=20$$$. Since $$$f(ABC) < f(AC),\,f(ABCD) > f(ACD)$$$, $$$f$$$ violates the dp property. In this case dij does not work, because dij uses ABC to slack D, giving a wrong result $$$24$$$ instead of the correct answer $$$20$$$.

We denote $$$d(v)$$$ as the real value of the shortest path (i.e., $$$\min f(\{p \mid p\,\text{is a S-v path}\}$$$), and $$$h(v)$$$ as the value calculated by dij. We want to prove $$$\forall v \in V(G),\,h(v) = d(v)$$$. We briefly review the outline of the dij:

define a distance array d. Initially fill d with INF;
Initialize f(s), h(s) for all source vertices s in S;
define a set T which is initially S;
int i = 0; //frame number

while T != V(G){
    choose a vertex u that is not in T with the lowest h value; //Choice step
    for every vertice v not in T and adjacent to u, update h(v) as h(v) = min(h(v), f([path from S to u] + v)). //You can record the shortest path from S to v here; //Slack step
    T.insert(u);
    i++;
}

Here, I want to illustrate the importance of these properties by proving the correctness of the algorithm.

In the induction step, the $$$d$$$ is correctly computed for every source vertex. In the $$$i$$$-th frame, a vertex $$$u$$$ is chosen in the choice step. We assume that for every $$$v$$$ chosen in the choice step of $$$0,\,1,\,2...\,i-1$$$ frames, $$$h(v) = d(v)$$$. For the $$$i$$$-th frame, I am going to show $$$h(u) = d(u)$$$. Consider the shortest path from $$$S$$$ to $$$u$$$ (we call it $$$S-u$$$ path, and it must exist since the graph is finite), and denote $$$y$$$ as the last vertex that does not belong to $$$T$$$:

In the following proof, $$$S-x$$$ means a path from S to $$$x$$$. It is not set difference.

First, for all source vertices, i.e., $$$\forall s \in S$$$, we have $$$h(s) = d(s)$$$. That is property 1, induction base.

(1) $$$h(u) \leq h(y)$$$. That is irrelevant to these properties, because dij always choose the vertex $$$u \notin T$$$ with the lowest $$$h$$$ value, if $$$h(u) > h(y)$$$, dij will not choose $$$u$$$ in this frame.

(2) $$$d(y) \leq d(u)$$$. This uses the extension property. $$$S-u$$$ path is shortest, so $$$f(S-u)=d(u)$$$. Due to the extension property, $$$f(S-y) \leq f(S-u)$$$. Since $$$d(y) = \min \text{all}\,f(S-y)\,\text{paths}$$$, we get $$$d(y) \leq d(u)$$$.

(3) $$$h(y) \leq f(S-x-y)$$$. This is irrelevant to these properties. That is because vertex $$$x$$$ is slacked using $$$f$$$.

(4) $$$h(x) = d(x)$$$. This is the induction hypothesis.

(5) $$$d(y) = f(S-x-y)$$$. This uses the dp property. The dp property guarantees that, if $$$\{v_1, v_2, ..., v_n\}$$$ is the shortest path from $$$v_1$$$ to $$$v_n$$$, then for $$$\forall 1 \leq k \leq n$$$, $$$\{v_1, v_2, ..., v_k\}$$$ is the shortest $$$v_1$$$-$$$v_k$$$ path.

Теги 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)