Thuật toán Dijkstra tìm đường đi ngắn nhất từ một đỉnh-- Dijkstra Algorithm

Trong bài này chúng ta sẽ tìm hiểu một thuật toán kinh điển tìm đường đi ngắn nhất từ một đỉnh tới mọi đỉnh khác trong đồ thị có hướng, có trọng số. Thuật toán này cũng áp dụng được cho đồ thị vô hướng nếu như ta coi mỗi cạnh vô hướng uv là 2 cung có hướng ngược chiều nhau u\rightarrow vv\rightarrow u với cùng trọng số của cạnh uv. Do đó, ta chỉ phát biểu thuật toán trong bài này cho đồ thị có hướng mà thôi.

Các khái niệm cơ bản về cạnh, đường đi, chu trình, etc., mình đã viết ở bài trước nên ở đây mình không nhắc lại nữa. Ta gọi w: \vec{E} \rightarrow \mathbb{R}^+ là một hàm trọng số gán cho mỗi cung (u\rightarrow v) một trọng số w(u \rightarrow v) không âm. Đôi khi ta cũng có thể gọi trọng số của một cung là chiều dài của cung đó. Chiều dài của một đường đi P(u,v) giữa hai điểm được định nghĩa là tổng chiều dài của các cạnh nằm trên đường đi đó và ta kí hiệu là w(P(u,v)). Bài toán mà chúng ta sẽ tìm hiểu trong bài này như sau:

Problem 1: Cho một đồ thị có hướng G(V,\vec{E}), một hàm trọng số w : \vec{E} \rightarrow \mathbb{R}^+ và một đỉnh s. Tìm đường đi ngắn nhất từ s tới mọi đỉnh trong G.

 

Để đơn giản, ta sẽ dùng VE lần lượt để chỉ số đỉnh và số cạnh của đồ thị. Năm 1959, Dijkstra[1] công bố thuật toán Dijkstra giải bài toán này trong thời gian O(V^2). Thuật toán Dijkstra là tối ưu với đồ thị dày (E = O(V^2)) nhưng với đồ thị thưa thì thuật toán này khá chậm. Tuy nhiên, ý tưởng của Dijkstra sau này đã được cải tiến [3] và có thời gian chạy O(E + V\log V) . Trong bài này, chúng ta sẽ tìm hiểu một phiên bản thực thi thuật toán đó sử dụng Heap nhị phân trong thời gian O((V+E)\log V). Cuối bài, mình sẽ thảo luận ngắn gọn thuật toán O(E + V\log V) với Fibonacci Heap của Fredman và Tarjan.

Theorem 1: Thuật toán Dijkstra tìm đường đi ngắn nhất từ một đỉnh tới mọi đỉnh khác trong đồ thị với thời gian O((V+E)\log V).

 

Tính chất của đường đi ngắn nhất

Gọi \delta(s,v) là khoảng cách ngắn nhất từ s tới v trong GSP(s,v) là một đường đi ngắn nhất bất kì từ s tới v. Ta có:

Lemma 1: Đường đi con của SP(s,v) từ s tới một đỉnh u \in SP(s,v) cũng là đường đi ngắn nhất từ s tới u.

 

Chứng minh: Gọi P(s,u) là đường đi con của SP(s,v) từ s tới u. Giả sử tồn tại một đường đi khác P'(s,u) sao cho w(P'(s,u)) < w(P(s,u)). Thay thế đường đi P(s,u) trong SP(s,v) bằng đường đi P'(s,u) , ta sẽ thu được đường đi khác từ s tới v với chiều dài nhỏ hơn, trái ngược với định nghĩa SP(s,v) là đường đi ngắn nhất.


Thuật toán Dijkstra

Experimental Thought Trước hết ta xét s và các hàng xóm của nó, gọi là tập N(s). Gọi u là một hàng xóm với độ dài cạnh w(s\rightarrow u) nhỏ nhất. Khoảng cách ngắn nhất từ s tới u là bao nhiêu? Câu trả lời chính là w(s \rightarrow u), vì nếu không, đường đi ngắn nhất từ s tới u đó phải đi qua một hàng xóm khác của s, và do đó, sẽ dài hơn w(s\rightarrow u). Từ đó ta suy ra \delta(s,u) = w(s\rightarrow u). Xem hình (b) ở hình dưới đây. Đỉnh được tô màu vàng đậm (đỉnh b) là đỉnh có trọng số cạnh từ s nhỏ nhất.

Tiếp theo ta xét tập các hàng xóm của cả su (u chính là b trong hình minh họa (c)), gọi là tập N(s,u). Với mỗi v \in N(s,u), ta gọi d[v] = \min(w(s\rightarrow v), \delta(s,u) + w(u \rightarrow v)). Dễ thấy nếu d[v] = w(s\rightarrow v), độ dài cạnh w(s\rightarrow v) sẽ nhỏ hơn độ dài đường đi s\rightarrow u \rightarrow v, và ngược lại. Trong số các đỉnh của tập N(s,u), gọi v là đỉnh có d[v] nhỏ nhất, i.e, v = \mathrm{argmin}_{x \in N(s,u)}(d[x]). Câu hỏi cũ vẫn là khoảng cách ngắn nhất từ s tới v là bao nhiêu? Dễ dàng thấy rằng \delta(s,v) = d[v] với cùng lí do như trên. Xem hình (c) trong hình dưới đây. Đỉnhh được tô màu hồng đậm là các đỉnh đã tìm được đường đi ngắn nhất. Đỉnh c là đỉnh có d[.] nhỏ nhất, do đó, d = \delta(s,c).

Tiếp theo ta lại xét N(s,u,v), blah. blah...(Xem hình (d)) Cứ tiếp tục lặp lại như vậy, ta sẽ tìm ra được đường đi ngắn nhất (chính xác phải là độ dài của đường đi ngắn nhất) từ s tới mọi đỉnh trong đồ thị. Đó chính là tư tưởng của thuật toán Dijkstra.
shortest-path-execution

Giả mã "thô" của thủ tục trên như sau:

Dijkstra(G(V,\vec{E}), w, s):
    for v \leftarrow 1 to V
        d[v] \leftarrow +\infty
    d[s] \leftarrow 0
    for every neighbor v of s
        d[v] \leftarrow w(s\rightarrow v)
    B \leftarrow V \backslash \{s\}         \ll B contains all vertices except s\gg
    repeat
        u \leftarrow \mathrm{argmin}_{x \in B} d[x]
        B \leftarrow B\setminus \{u\}         \ll d[u] = \delta(s,u)\gg
        for every neighbor v of u
            d[v] \leftarrow \min(d[v], d[u] + w(u\rightarrow v))
    until B = \emptyset

 

Ta có:

Theorem 2: Với mỗi đỉnh u, giá trị d[u] sau khi thực hiên Dijkstra(G(V,\vec{E}), w, s) là đường đi ngắn nhất từ s tới u.

 
Chứng minh Nhận thấy mỗi bước trong vòng lặp, ta sẽ lấy ra đúng một đỉnh khỏi tập B, do đó vòng lặp này thực hiện n-1 lần, trong đó n = V là số đỉnh. Gọi u_1,u_2,\ldots, u_{n-1} là thứ tự các đỉnh được lấy ra khỏi B theo thuật toán trên. Theo thảo luận ở phần experimental thought, d[u_1] = \delta(s,u_1) do u_1 là đỉnh có w(s\rightarrow u_1) nhỏ nhất trong số các hàng xóm của s.

Gọi d^i[v] là giá trị d[v] ngay trước vòng lặp i của thuật toán. Ta có d^i[v] chính là chiều dài của đường đi ngắn nhất từ s tới v đi qua một hoặc nhiều (hoặc 0) điểm trong tập \{u_1,u_2,\ldots, u_{i-1}\}. Vì u_i là đỉnh được lấy ra khỏi B ở bước thứ i, ta có:

d^i[u_i] \leq d^i[u_j] với mọi i+1 \leq j \leq n-1 \qquad (1)

Giả sử d^i[u] \not= \delta(s,u_i), đường đi ngắn nhất từ s tới u_i, SP(s,u_i), sẽ phải đi qua một đỉnh nào đó không thuộc \{u_1,\ldots, u_{i-1}\}. Gọi x là điểm đầu tiên trên đường đi từ s tới u thỏa mãn tính chất đó. Theo Lemma 1, đường đi con của SP(s,u_i) từ s tới x sẽ là đường đi ngắn nhất từ s tới x đi qua các điểm \{u_1,\ldots, u_{i-1}\}. Do đó d^i[x] = \delta(s,x). Từ đó ta suy ra d^i[x] < d^i[u]\delta(s,x) \leq w(SP(s,u_i)) < d^i[u]. Điều này trái với bất đẳng thức (1).


Áp dụng thuật toán Dijkstra với hình trên, ta thu được (cây) đường đi ngắn nhất trong hình sau:

shortest-path-complete-example

Các cung màu xanh là các cung của cây đường đi ngắn nhất. thứ tự các đinh được lấy ra từ B sẽ có chiều tăng dần của khoảng cách \delta(s,.).

Thực thi thuật toán Dijkstra

Bây giờ ta sẽ thực thi thuật toán trong giả mã ở trên. Như đã phân tích, vòng lặp repeat/until thực hiện V-1 lần lặp. Hai thao tác tốn kém nhất của mỗi lần lặp là:

  1. Lấy đỉnh u có giá trị d[u] nhỏ nhất ra khỏi B
  2. Cập nhật nhãn d[v] của các hàng xóm v của u.

Ta có thể thực thi tập hợp B mảng. Do đó, thao tác đầu tiên có thể thực hiện trong thời gian O(V) còn thao tác thứ 2 có thể thực hiện trong thi gian O(\deg(u)) trong đó \deg(u) là bậc của đỉnh u trong G (nếu sử dụng cấu trúc danh sách kề). Như vậy, ta có thể thực thi thuật toán trong thời gian:

O(V^2 + \sum_{u\in G} {\deg(u)}) = O(V^2 + E) = O(V^2)\qquad(2)

Tuy nhiên, nếu biểu diễn B bằng một Heap nhị phân, thao tác đầu tiên chính là ExtractMin và thao tác thứ 2 là DecreaseKey. Do mỗi thao tác ExtractMinDecreaseKey mất thời gian O(\log n), thời gian để thực hiện thuật toán Dijkstra với Heap nhị phân là:

O(V\log V + \sum_{u\in G} \log(V){\deg(u)}) = O((V+ E)\log V) \qquad(3)

Từ đó ta suy ra Theorem 1.

Giả mã của thuật toán:

DijkstraHeapA(G(V,\vec{E}), w, s):
    for v \leftarrow 1 to V
        d[v] \leftarrow +\infty
    d[s] \leftarrow 0
    for every neighbor v of s
        d[v] \leftarrow w(s\rightarrow v)
    B \leftarrow BuildHeap(V\setminus \{s\})         \ll B contains all vertices except s\gg
    repeat
        u \leftarrow ExtractMin(B)         \ll d[u] = \delta(s,u)\gg
        for every neighbor v of u
            d[v] \leftarrow \min(d[v], d[u] + w(u\rightarrow v))
            DecreaseKey(B,v, d[v])
    until B = \emptyset

 

Remark Nếu ta biểu diễn B bằng Fibonacci Heap, thao tác ExtractMin có thời gian O(\log n) (khấu trừ) và thao tác DecreaseKey có thời gian O(1). Do đó, tổng thời gian của thuật toán Dijkstra với Fibonacci Heap là:

O(V\log V + \sum_{u\in G} {\deg(u)}) = O((V\log V + E) \qquad(4)

Để in ra đường đi ngắn nhất, mỗi khi cập nhật lại giá trị d[v] \leftarrow \min(d[v], d[u] + w(u\rightarrow v)) trong thuật toán trên, ta sẽ đánh dấu u là hàng xóm làm thay đổi nhãn d[v] của v. Ta sẽ dùng một mảng P và đánh dấu P[v] = u. Như vậy, thuật toán cuối cùng như sau:

DijkstraHeapB(G(V,\vec{E}), w, s):
    for v \leftarrow 1 to V
        d[v] \leftarrow +\infty
    d[s] \leftarrow 0
    P[s] \leftarrow s
    for every neighbor v of s
        d[v] \leftarrow w(s\rightarrow v)
        P[v] \leftarrow s
    B \leftarrow BuildHeap(V\setminus \{s\})         \ll B contains all vertices except s\gg
    repeat
        u \leftarrow ExtractMin(B)         \ll d[u] = \delta(s,u)\gg
        for every neighbor v of u
            if d[v] > d[u] + w(u\rightarrow v))
                d[v] \leftarrow d[u] + w(u\rightarrow v)
                P[v] \leftarrow u

            DecreaseKey(B,v, d[v])
    until B = \emptyset

 

FindReverseShortestPath(G(V,\vec{E}),w,s,t):
    DijkstraHeapB(G, w,s)
    print t
    while P[t] \not= t
        t \leftarrow P[t]
        print t

 

Code C với biểu diễn ma trận kề:

 
int **W;	// the weight matrix
int n;		// the number of vertices of the graph
int *D;		// the distance array
int *P;		// the parent array

void dijkstra_heap(int** W, int s, int n){
	P = (int *)malloc(n*sizeof(int));
	D = (int *)malloc(n*sizeof(int));
	int i = 0;
	for(; i < n; i++)D[i] = INFTY;
	D[s] = 0;
	P[s] = s;
	int v = 0;
	for(; v < n; v++){
		if(W[s][v] < INFTY){
			D[v] = W[s][v];
			P[v] = s;
		}
	}
	build_heap(n,s);
	int u;
	while(hsize != 0){ 	// the heap is not empty
		u = extract_min();
		for(v = 0; v < n; v++){
			if(D[v] > D[u] + W[u][v]){
				D[v] = D[u] + W[u][v];
				P[v] = u;
				decrease_key(v,D[v]);
			}

		}
	}
}

void print_reverse_path(int t){
	printf("%d ",t);
	while(P[t]!= t){
		t = P[t];
		printf("%d ",t);
	}
	printf("\n");
}

Nhắc lại Heap nhị phân

Chúng ta sẽ phải sửa đổi lại một chút mã của Heap nhị phân trong bài trước để áp dụng vào thuật toán Dijkstra. Trong bài trước, chúng ta sử dụng mảng H[1,2,\ldots,n] để thực thi Heap, trong đó phần tử H[i] lưu giá trị khóa tương ứng với nút thứ i. Do đó, khi cập nhật một giá trị khóa sử dụng DecreaseKey ta cần phải có địa chỉ của nút cần cập nhật và giá trị khóa mới của nút đó.

Với thuật toán Dijkstra, ta vẫn sử dụng mảng H[1,2,\ldots,n] để thực thi Heap. Tuy nhiên, mỗi phần tử H[i] sẽ lưu một đỉnh của đồ thị (chứ không phải khóa) còn khóa sẽ được lưu trong mảng d. Như vậy, khóa của nút thứ i của Heap là d[H[i]]. Để thực hiện DecreaseKey, như đã nói ở đoạn văn trước, ta sẽ lưu một mảng pos[1,2,\ldots, V] trong đó pos[v] sẽ lưu vị trí của đỉnh v \in G trong Heap H. Hay nói cách khác,

pos[v] = i khi và chỉ khi H[i] = v \qquad (4)

Giả mã của Heap:

DecreaseKey(Heap H, Vertex u, Key K):
    D[u] \leftarrow K
    UpHeapify(pos[u])

 

ExtractMin(Heap H):
    n \leftarrow length of the heap H
    tmp \leftarrow H[1]
    H[1] \leftarrow H[n]
    pos[H[n]] \leftarrow 1         \ll update the position of the vertex H[n] \gg
    n \leftarrow n-1
    DownHeapify(1)
    return tmp

 

DownHeapify( Heap Node u):
    m \leftarrow 2*u         \ll v is the left child of u \gg
    if m \leq n         \ll u is not a leaf\gg
        if d[H[m]] > d[H[2*u+1]]
            m \leftarrow 2*u+1
        if d[H[u]] > d[H[m]]
            swap H[u] \leftarrow H[m]
            update pos H[u] and H[m] after swap
            DownHeapify(m)

 

Parent( u):
    if u is even
        return u/2
    else
        return (u-1)/2

 

BuildHeap(V\setminus\{s\}):
    for i \leftarrow 1 to s-1
        H[i] \leftarrow i
        pos[i] \leftarrow i
    for i \leftarrow s+1 to V
        H[i-1] \leftarrow i
        pos[i] \leftarrow i-1
    for i \leftarrow V-1 down to 1
        DownHeapify(i)

 

Code C:

int *H; 	// the Heap array
int hsize = 0; 	// the number of elements in the current Heap
int *pos;	// the array marks position of each vertex in the Heap array


void decrease_key(int u, int k){
	D[u] = k;
	up_heapify(pos[u]);
}

int extract_min(){
	int tmp  = H[0];
	H[0] = H[hsize-1];
	pos[H[0]] = 0;
	hsize--;
	down_heapify(0);
	return tmp;
}

void up_heapify(int u){
	int v = parent(u);
	if(v != -1 && D[H[u]] < D[H[v]]){ // u is not the root of the heap
		int tmp = H[u];
		H[u] = H[v];
		pos[H[v]] = u;		// update the position of node H[v] in the Heap
		H[v] = tmp;
		pos[tmp] = v;		// update the position of node tmp in the Heap
		up_heapify(v);
	}
}

void down_heapify(int u){
	int m = 2*u+1;
	if(m < hsize){	// u is not a leaf of the heap
		if(2*u+2 < hsize && D[H[m]] > D[H[2*u+2]]){
			m = 2*u+2;		
		}
		if(D[H[u]] > D[H[m]]){
			int tmp = H[u];
			H[u] = H[m];
			pos[H[m]] = u;	// update position of node H[m] in the Heap
			H[m] = tmp;
			pos[tmp] = m;	// update the position of node tmp in the Heap
			down_heapify(m);		
		}
	}
}

// Note that array in C is indexed from 0 
// Two children of a node u is 2u+1 and 2u+2, the smaller one is the left child

int parent(int u){
	return ((u&1)==0 ? ((u-2)>> 1) : (u-1) >> 1);
}

// Build the heap from an array in O(n) time
void build_heap(int n, int s){
	hsize = n-1;
	H = (int *)malloc(hsize*(sizeof(int)));
	pos = (int *)malloc(hsize*sizeof(int));
	int i = 0;
	for(; i < s; i++) {
		H[i] = i;
		pos[i] = i;
	}

	for(i = s+1; i < n; i++){
		H[i-1]=i;
		pos[i] = i-1;
	}
	for(i = hsize-1; i >=0; i--){
		down_heapify(i);
	}
}

Code đầy đủ: Dijkstra-with-adjacency-matrix, Dijkstra-with-adjacency-list

Tham khảo

[1] Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1: 269–271
[2] Jeff Erickson. Lecture Notes on Single Source Shortest Paths. UIUC, 2014.
[3] Fredman, Michael L., and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM) 34.3 (1987): 596-615.

Tags: , , , , , ,

Reply

Your email address will not be published. Required fields are marked *