Dijkstra

You are currently browsing articles tagged Dijkstra.

Chúng ta đã tìm hiểu thuật toán Floyd-Warshall tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong thời gian $O(n^3)$. Thuật toán này áp dụng được cho cả trường hợp đồ thị có trọng số âm và không có chu trình âm. Cho đến nay vẫn chưa có thuật toán nào thực sự nhanh hơn $O(V^3)$ một cách đáng kể (xem lại phần Remark cuối cùng của bài Floyd-Warshall).

Với đồ thị không có trọng số âm, chúng ta cũng đã biết rằng áp dụng thuật toán Dijkstra (với Fibonacci Heap) $V$ lần, ta sẽ thu được thuật toán $O(VE + V^2\log V)$. Với đồ thị thưa ($E = o(V^2)$), thuật toán này rõ ràng nhanh hơn $O(V^3)$ một cách đáng kể. Ở đây mình nhấn mạnh đồ thị không có trọng số âm thì ta mới áp dụng Dijkstra được. Vấn đề của bài này là đồ thị có trọng số âm:

Problem 1: Có tồn tại hay không thuật toán $O(VE + V^2\log V)$ tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị có hướng, có trọng số và không có chu trình âm?

 

Năm 1977, Johnson [1] đưa ra câu một câu trả lời cho câu hỏi trên:

Theorem 1: Thuật toán Johnson tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị có hướng, có trọng số và không có chu trình âm trong thời gian $O(VE + V^2\log V)$.

 

Remark cũng trong bài báo [1], Johson giới thiệu cấu trúc Heap $d$-phân để thực thi Dijkstra mà ta đã tìm hiểu ở bài thực thi thuật toán Dijkstra.

Ý tưởng của thuật toán Johnson:

Ý tưởng: Thay đổi trọng số của các cung của $G$ để thu được đồ thị $H$ sao cho: (i) trọng số cung của đồ thị $H$ không âm; do đó ta có thể áp dụng Dijkstra cho $H$ để tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong $H$ và (ii) đường đi ngắn nhất giữa hai đỉnh bất kì của $H$ cũng chính là đường đi ngắn nhất giữa hai đỉnh tương ứng của $G$.

Ta gọi thủ tục để thực hiện ý tưởng trên là một phép quy dẫn (reduction) từ $G$ về $H$. Khái niệm quy dẫn là khái niệm mà ta sẽ rất hay gặp trong lý thuyết độ phức tạp của thuật toán. Chú ý là hai đồ thị $G$ và $H$ có cùng tập đỉnh và tập các cung (trọng số của các cung có thể khác nhau).

Để phát biểu thuật toán một cách tỉ mỉ hơn, ta cần thêm một số định nghĩa và khái niệm. Với mỗi đường đi $P(s,t)$ giữa hai đỉnh bất kì $s,t$ trong đồ thị, ta định nghĩa độ lệch của đường đi (kí hiệu $\Phi_P(s,t)$) bằng trọng số của đường đi đó trong $H$ trừ đi trọng số của cùng đường đi trong $G$. Một cách hình thức:

$\Phi_P(s,t) = w(P(s,t),H) - w(P(s,t),G) \qquad (1)$

trong đó kí hiệu $w(P(s,t),G)$ (hoặc $w(P(s,t),H)$) là trọng số của đường đi $P(s,t)$ trong $G$ ( hoặc $H$).

Một cách đơn giản nhất để thực hiện (i) đó là cộng trọng số của tất cả các cung của $G$ với cùng một trọng số $W$ đủ lớn để thu được $H$ mọi cung đều không âm. Sau đó từ đường đi ngắn nhất giữa hai đỉnh trên đồ thị $H$, với mỗi cung trên đường đi, ta trừ $W$ đơn vị trọng số để thu được đường đi ngắn nhất trong $G$.

Cách làm trên thoạt đầu nghe có vẻ đúng nhưng thực tế là sai (tại sao?). Tuy nhiên tư tưởng của nó vẫn được Johnson áp dụng trong thuật toán của mình. Thay vì cộng tất cả các cung với cùng một trọng số, Johnson cộng với mỗi cung $ u\rightarrow v$ một trọng số phụ thuộc vào chính cung này. Cụ thể, trọng số $w(u\rightarrow v)$ sẽ được cộng với một số $p(u \rightarrow v)$ sao cho trọng số mới thu được, $\Delta(u\rightarrow v)$ thỏa mãn:

$\Delta(u\rightarrow v) = w(u\rightarrow v) + p(u\rightarrow v) \geq 0 \qquad (2)$

Để đảm bảo đường đi ngắn nhất giữa bất kì hai đỉnh $s,t$ nào trong $H$ cũng là đường đi ngắn nhất giữa $s$ và $t$ trong $G$ và ngược lại, ta phải đảm bảo:

Nếu $Q(s,t)$ và $P(s,t)$ là hai đường đi giữa $s$ và $t$ thỏa mãn $w(P(s,t), G) < w(P(s,t), G)$ thì $w(P(s,t), H) < w(Q(s,t), H)$.

Như vậy, quan hệ "ngắn hơn" giữa hai đường đi bất kì với cùng điểm đầu điểm cuối phải được bảo toàn khi ta quy dẫn $G$ về $H$. Johnson đảm bảo điều này bằng cách chọn $p(u\rightarrow v)$ sao cho mọi đường đi từ $s$ tới $t$ đều có cùng độ lệch.

$\Phi_P(s,t) = \Phi_{Q}(s,t) = \Phi(s,t)\qquad (3)$

với mọi $P(s,t), Q(s,t)$ là hai đường đi khác nhau bất kì từ $s$ tới $t$ và $\Phi(s,t)$ là hàm chỉ phụ thuộc vào $s,t$. Ta sẽ chứng minh:

Claim 1: Nếu ta chọn $p(u\rightarrow v)$ với mỗi cung $(u\rightarrow v) \in \vec{E}$ sao cho độ lệch của mọi đường đi giữa hai đỉnh $s,t$ bất kì thỏa mãn $(3)$ thì quan hệ "ngắn hơn" sẽ được bảo toàn.

 
Chứng minh: Giả sử $P(s,t)$ và $Q(s,t)$ là hai đường đi bất kì giữa $s$ và $t$ thỏa mãn: $w(P(s,t), G) < w(P(s,t), G)$. Do $\Phi_P(s,t) = \Phi_Q(s,t) = \Phi(s,t)$, ta có:

$w(P(s,t), G) + \Phi_P(s,t) < w(P(s,t), G) + \Phi_Q(s,t)$

Theo định nghĩa:

$w(P(s,t), H) = w(P(s,t), G) + \Phi_P(s,t)$ và $w(Q(s,t), H) = w(Q(s,t), G) + \Phi_Q(s,t)$

Từ đó ta suy ra $w(P(s,t), H) < w(Q(s,t), H) $, đó là dpcm.


Bài toán của chúng ta bây giờ là đảm bảo:

Tính bất biến của độ lệch: Độ lệch của một đường đi chỉ phụ thuộc vào điểm đầu và điểm cuối mà không phụ thuộc vào chính đường đi đó.

Johson chọn $p (u\rightarrow v) = p(u) - p(v)$ với $p(x)$ là thế năng (potential) của đỉnh $x$ (ta sẽ mô tả chỉ tiết sau). Ta sẽ chứng minh với cách chọn như vậy, tính bất biến của độ lệch sẽ được thỏa mãn:

Lemma 1: Nếu chọn $p(u\rightarrow v)$ theo cách của Johnson thì ta có:

$\Phi(s,t) = p(s) - p(t) \qquad (4)$

trong đó $s,t$ là hai đỉnh bất kì thuộc đồ thị.

 

Chứng minh: Gọi $P(s,t) = v_0 = s, v_2,v_2,\ldots, v_k = t$ là một đường đi bất kì từ $s$ tới $t$. Theo định nghĩa ta có:

$\begin{array} {l} w(P(s,t,),H) & = \sum_{i=0}^{k-1}\Delta(v_i\rightarrow v_{i+1}) \\ & = \sum_{i=0}^{k-1}w(v_i\rightarrow v_{i+1}) + p(v_i) - p(v_{i+1}) \\ & = \sum_{i=0}^{k-1}w(v_i\rightarrow v_{i+1}) + \sum_{i=0}^{k-1}p(v_i) - p(v_{i+1}) \\ &= w(P(s,t),G) + \sum_{i=0}^{k-1}p(v_i) - p(v_{i+1}) \\ &= w(P(s,t),G) + p(v_0) - p(v_k) \\ &= w(P(s,t),G) + p(s) - p(t) \end{array} \qquad (5)$

Cũng theo định nghĩa, $\Phi_P(s,t) = w(P(s,t,),H) - w(P(s,t),G)$. Từ đó ta suy $\Phi_P(s,t) = p(s) - p(t)$; hay $\Phi_P(s,t)$ không phụ thuộc vào đường đi $P$. Đó là dpcm.


Chọn hàm thế năng

Ta phải chọn hàm thế năng $p: V \rightarrow \mathbb{R}$ sao cho bất đằng thức $(2)$ thỏa mãn với mọi cung $(u \rightarrow v)$. Do $ p(u\rightarrow v) = p(u) - p(v)$, bất đằng thức $(2)$ tương đường với:

$w(u\rightarrow v) + p(u) - p(v) \geq 0 \qquad (6)$

Bất đẳng thức này gợi lại cho ta bất đẳng thức tam giác: nếu $\delta(s,v)$ là khoảng cách ngắn nhất từ $s$ (nào đó) tới $v$ thì ta có:

$ \delta(s,v) \leq \delta(s,u) + w(u\rightarrow v) \qquad (7)$

Do đó, nếu chọn $p(x) = \delta(s,x)$ với mọi $x \in V$ thì bất đằng thức $(6)$ sẽ thỏa mãn với mọi cung $(u\rightarrow v)$.

Vấn đề còn lại là chọn $s$ như thế nào? Ta phải chọn $s$ sao cho đường đi ngắn nhất từ $s$ tới mọi đỉnh khác đều tồn tại, i.e, $\delta(s,x) < +\infty$ với mọi $x \in G$. Johnson làm như sau: Thêm vào $G$ một đỉnh $s$ và với mỗi đỉnh $x \in G$, thêm cung $(s\rightarrow x)$ với trọng số $w(s \rightarrow x) = 0$. Phép thêm đỉnh $s$ này sẽ đảm bảo : nếu $G$ không có chu trình âm thì $G\cup \{s\}$ cũng không có chu trình âm và ngược lại (chứng minh coi như bài tập cho bạn đọc).

Sau khi đã thêm $s$, ta sẽ áp dụng thuật toán Bellman-Ford để tìm khoảng đi ngắn nhất $\delta(s,x)$ trong thời gian $O(VE)$.

Thuật toán Johnson

Tổng kết lại thảo luận ở trên, thuật toán Johson có 4 bước:

  1. Thêm vào $G$ một đỉnh $s$ và với mỗi $x \in V$, thêm cung $(s\rightarrow x)$ có trọng số $w(s\rightarrow x) = 0$
  2. Áp dụng thuật toán Bellman-Ford tìm khoảng cách ngắn nhất $\delta(s,x)$ từ $s$ tới mọi $x \in V$ và sử dụng khoảng cách đó làm thế năng của đỉnh $x$, i.e, $p(x) = \delta(s,x)$.
  3. Gán cho mỗi cung $(u\rightarrow v) \in \vec{E}$ một trọng số mới $\Delta(u \rightarrow v) = w(u\rightarrow v) + p(u) - p(v)$. Gọi đồ thị với trọng số mới là $H$. Theo thảo luận ở trên, trọng số của $H$ là không âm.
  4. Áp dụng Dijkstra $V$ lần cho đồ thị $H$ để tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong $H$. Gọi $\delta_H(x,y), \delta(x,y)$ lần lượt là khoảng cách từ $x$ tới $y$ trong $H$ và $G$. Theo $(4)$, độ lệch của đường đi ngắn nhất từ $x$ tới $y$ chính là $\delta_H(x,y) - \delta(x,y) = p(x) - p(y)$. Từ đó suy ra:

    $\delta(x,y) = \delta_H(x,y) + p(y) - p(x) \qquad (8)$

Giả mã:

JohnSon($G(V,\vec{E}), w$):
    add $s$ to $V$
    for each $x \in V$
        add $(s\rightarrow x)$
        $w(s\rightarrow x) \leftarrow 0$
    $P[1,\ldots,V] \leftarrow $ BellmanFord($G, s, w$)         $\ll P[x] = \delta(s,x)\gg$
    for each arc $(u\rightarrow v) \in \vec{E}$
        $\Delta(u\rightarrow v) \leftarrow w(u\rightarrow v) + P[u] - P[v]$
    for each $x \in V$
        $D[x][1,\ldots, V] \leftarrow $ Dijkstra($G, x, \Delta$)
    for each $x \in V$
        for each $y \in V$
            $\delta(x,y) \leftarrow D[x,y] + P[y] - P[x]$

 

Code C:

#define INFTY 1000000000
// we use linked lists to represent adjacency lists
// each arc u-&gt;v with weight w(u-&gt;v) is represented by a node with data field v and weight w in the adacency list of u

typedef struct vlist{
int v;		// the head of the directed edge
int w;		// the original weight of the directed edge
int Delta;	// the modified weight using potential
struct vlist *next;
}vlist;

vlist **G;				// G[i] is the adjacency list of vertex i
int n;					// the number of vertices of the graph
int **D;				// the all-pair distance array of Johnson algorithm
int *d;					// the distance array for Dijkstra's algorithm

int **johnson(){
int s = n;				// add a new vertex s
int u = 0, v = 0;
for(; u &lt; n; u++){
add_arc(s,u,0);			// add an arc s-&gt;u of weight 0
}
int *P = bellman_ford(G,s,n+1);		// the distance array from Bellman-Ford algorithm
//loop through all arcs of G
for(u = 0; u &lt; n; u++){
vlist *nbrs = G[u];		// the head of the list of neighbors of u
while(nbrs != NULL){
v = nbrs-&gt;v;
nbrs-&gt;Delta = nbrs-&gt;w + P[u] - P[v];	// the modified weight
nbrs = nbrs-&gt;next;
}
}
printf("the graph after weight modification\n");
print_list_graph();
H = (int *)malloc((n-1)*(sizeof(int)));		// initialize the heap
pos = (int *)malloc((n-1)*sizeof(int));

int **D = (int **) malloc(n*sizeof(int*));		// initialize the all-pairs distance array ;
d = (int *)malloc(n*sizeof(int));			// initialize the distance array for Dijkstra;
for( u = 0; u &lt; n; u++){
D[u] = (int *)malloc(n*sizeof(int));
dijkstra_heap(G, u, n);	 	// the shortest distances from u to other vertices are stored in array d
for(v = 0; v &lt; n; v++){
D[u][v] = d[v] + P[v] - P[u];	// the real u to v distance
}
}

return D;
}

// The Bellman-Ford algorithm. See http://www.giaithuatlaptrinh.com/?p=789 for more details

int *bellman_ford(vlist **G, int s, int n){
int* D = (int *)malloc(n*sizeof(int));
int i = 0;
for(; i &lt; n; i++)D[i] = INFTY;
D[s] = 0;
int v = 0;
vlist *nbrs = G[s];	// the list of neighbors of s
while(nbrs != NULL){	// iterating over neighbors of s
v = nbrs-&gt;v;
D[v] = nbrs-&gt;w;	// nbrs-&gt;w = w(s-&gt;v)
nbrs = nbrs-&gt;next;
}
int  u = 0;
for(i = 0; i &lt; n-2; i++){
for(u = 0; u &lt; n; u++){
vlist *nbrs = G[u];	// the list of neighbors of u
while(nbrs != NULL){	// iterating over neighbors of u
v = nbrs-&gt;v;
if(D[v] &gt; D[u] + nbrs-&gt;w){	// the arc u-&gt;v is tense
D[v] = D[u] + nbrs-&gt;w;	// nbrs-&gt;w = w(u-&gt;v)
}
nbrs = nbrs-&gt;next;
}
}
}
return D;
}

// The Dijkstra algorithm with Binary Heap. See  http://www.giaithuatlaptrinh.com/?p=764 for more details
// Note here that we are running Dijkstra with new weight function Delta
void dijkstra_heap(vlist** G, int s, int n){
int i = 0;
for(; i &lt; n; i++)d[i] = INFTY;
d[s] = 0;
int v = 0;
vlist *nbrs = G[s];	// the list of neighbors of s
while(nbrs != NULL){	// iterating over neighbors of s
v = nbrs-&gt;v;
d[v] = nbrs-&gt;Delta;	// nbrs-&gt;Delta = Delta(s-&gt;v)
nbrs = nbrs-&gt;next;
}
build_heap(n,s);
int u;
while(hsize != 0){ 	// the heap is not empty
u = extract_min();
vlist *nbrs = G[u];	// the list of neighbors of u
while(nbrs != NULL){	// iterating over neighbors of u
v = nbrs-&gt;v;
if(d[v] &gt; d[u] + nbrs-&gt;Delta){
d[v] = d[u] + nbrs-&gt;Delta;	// nbrs-&gt;w = w(u-&gt;v)
decrease_key(v,d[v]);
}
nbrs = nbrs-&gt;next;
}
}
}

Phân tích thời gian: Ta sẽ phân tích từng bước trong mô tả ở trên. Bước (1) mất thời gian $O(V)$. Bước (2) mất thời gian $O(VE)$ (xem lại bài Bellman-Ford). Bước (3) mất thời gian $O(E)$. Bước (4) áp dụng $V$ lần Dijkstra cho đồ thị $H$; bước này, như đã chỉ ra ở trên, mất thời gian $O(VE + V^2\log V)$. Do đó, tổng thời gian của thuật toán là $O(VE + V^2\log V)$.

Ví dụ:

johnson-alg-ex

Hình (a) là đồ thị có hướng $G$ mà ta muốn tìm đường đi ngắn nhất. Hình (b) là đồ thị thu được sau khi ta thêm $s$ và các cung (gạch và có màu đó) có hướng từ $s$ tới các đỉnh khác với trọng số 0. Hình (c) là cây đường đi ngắn nhất gốc tại $s$ sau khi áp dụng thuật toán Bellman-Ford. Các số trong ô vuông chính là khoảng cách từ $s$ tới đỉnh tương ứng. Hình (d) là đồ thị $H$ thu được sau khi hiệu chỉnh trọng số của $G$ theo công thức $8$.

Code đầy đủ: Johnson-algorithm.

Tham khảo

[1] Johnson, Donald B. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM (JACM) 24.1 (1977): 1-13.
[2] Uri Zwick. Computing shortest paths and detecting negative cycles, Lecture notes for "Analysis of Algorithms", 2009.

Tags: , , , , ,

« Older entries