heap

You are currently browsing articles tagged heap.

Trong bài này chúng ta sẽ tìm hiểu các cách thực thi khác nhau của thuật toán Dijkstra sử dụng các cấu trúc dữ liệu. Bài này chủ yếu dựa trên Chương 4 của [1]. Mặc dù thuật toán $O(m + n\log n)$ sử dụng Fibonacci Heap là thuật toán tối ưu trong trường hợp tổng quát, trong một số trường hợp đặc biệt, sử dụng các cấu trúc dữ liệu khác sẽ cho chúng ta thời gian tốt hơn nhiều.

Trong bài giới thiệu về đồ thị, chúng ta đã biết thuật toán BFS, trong trường hợp đồ thị không có trọng số, sẽ cho chúng ta đường đi ngắn nhất trong thời gian tuyến tính $O(m+n)$. Nếu đồ thị có trọng số là các số nguyên không quá lớn thì liệu chúng ta có thể có cách thực thi với thời gian tuyến tính hay không? Nếu đồ thị là thưa (số cạnh tuyến tính với số đỉnh) thì chúng ta có thể thực hiện được nhanh hơn $O(m+n\log n)$ không? Bài này sẽ trả lời những câu hỏi như vậy.

Problem 1: Cho đồ thị $G(V,\vec{E})$ có hướng với các cạnh có trọng số không âm và một đỉnh $v$ thuộc đồ thị, tìm đường đi ngắn nhất từ $v$ tới mọi đỉnh khác trong đồ thị.

 

Nhắc lại thuật toán Dijkstra

Các bạn xem chi tết thuật toán thuật toán Dijkstra tại bài viết trước. Phần này mình sẽ nhắc lại tư tưởng chính. Thuật toán Dijkstra sẽ tìm cây đường đi ngắn nhất $T_v$ gốc tại $v$, trong đó đường đi từ $v$ đến bất kì một đỉnh nào trong cây chính là đường đi ngắn nhất từ $v$ tới đỉnh đó của đồ thị $G$. Ban đầu cây $T_v$ được khởi tạo chỉ gồm một đỉnh $v$. Mỗi bước, thuật toán sẽ thêm một đỉnh vào cây cho đến khi cây $T_v$ chứa tất cả các đỉnh của đồ thị.

Để xác định đỉnh nào sẽ được thêm vào đồ thị, thuật toán sẽ duy trì, với mỗi đỉnh $u$, một ước lượng của đường đi ngắn nhất $d[u]$. Ước lượng này ban đầu sẽ được khởi tạo là $d[u] \leftarrow w(v\rightarrow u)$. Quy tắc thêm đỉnh vào $T_v$ như sau: Trong các đỉnh còn lại của đồ thị không thuộc $T_v$, thêm vào $T_v$ đỉnh $u$ có khoảng cách ước lượng đến $v$ là nhỏ nhất. Sau khi thêm $u$ vào $T_v$, ta phải cập nhật lại ước lượng của các đỉnh khác: với mỗi $x$, gán $d[x] \leftarrow d[u] + w(u\rightarrow x)$ nếu $d[x] > d[u] + w(u\rightarrow x)$. Ý nghĩa của việc gán này là đường đi từ $v$ qua $u$ tới $x$ sẽ ngắn hơn ước lượng hiện tai của $x$ và do đó, ta phải cập nhật lại $d[x]$. Chứng minh tính đúng đắn của quy luật thêm đỉnh vào $T_v$, bạn đọc xem lại bài viết trước.

Dễ thấy thuật toán sẽ kết thúc sau $V-1$ bước. Thời gian thực hiện của mỗi bước sẽ phụ thuộc vào hai thao tác:

  1. Tìm ra đỉnh $u$ có ước lượng $d[u]$ nhỏ nhất trong số các đỉnh không thuộc $T_v$
  2. Cập nhật lại các đỉnh $d[x]$ của các đỉnh $x$ sau khi đã thêm $u$ vào $T_v$

 

Nếu sử dụng mảng để lưu trữ các giá trị $d[u]$, thao tác (1) có thể thực hiện trong thời gian $O(V)$, thao tác (2) có thể thực hiện trong thời gian $O(1)$ với mỗi đỉnh $x$ (có $d^{-}(u)$ đỉnh như vậy). Do đó, tổng thởi gian thời gian thực thi của thuật toán là:

$O(V^2) + \sum_{u\in V}d^{-}(u) = O(V^2 + E) = O(V^2) \qquad (1)$

Nếu ta sử dụng Heap để lưu trữ các giá trị $d[u]$, thao tác (1) sẽ tương đương với thao tác ExtractMin và thao tác thứ (2) sẽ tương đương với thao tác DecreaseKey.

Nếu Heap mà chúng ta sử dụng là Heap nhị phân, thì thao tác (1) và (2) có thể thực hiện trong $O(\log V)$. Do đó tổng thời gian của thuật toán Dijkstra với Heap nhị phân là:

$O(V\log V) + \sum_{u\in V}d^{-}(u)\log V = O(V\log V + E\log V) = O(E\log V) \qquad (2)$

Nếu Heap mà chúng ta sử dụng là Fibonacci Heap , thì thao tác (1) có thể thực hiện trong $O(\log V)$ và (2) có thể thực hiện trong $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 V}d^{-}(u) = O(V\log V + E) \qquad (3)$

Tuy có thời gian tiệm cận khá tốt, nhưng Fibonacci Heap ít được dùng trong thực thì vì thực thi phức tạp và hằng số ẩn sau kí hiệu Big-O khá lớn.

Cấu trúc Heap $d$-phân

Thay vì dùng Heap nhị phân, ta sẽ sử dụng Heap tam phân, tứ phân, hay tổng quát là $d$-phân. Ý tưởng này được đề xuất bởi Johnson [3]. Heap $d$-phân là một (min) Heap trong đó mỗi nút trong Heap có $d$ nút con. Cách thức thực thi giống như Heap nhị phân (các bạn xem lại bài Heap nhị phân). Ví dụ Heap $3$-phân tập các phần tử $\{1,3,7,2,7,5,9,9,8\}$ được minh họa trong hình dưới đây:

3-heap

Ta sẽ thực thi Heap bằng một mảng $H[1,\ldots, V]$, trong đó:

  • $H[1]$ sẽ là gốc của Heap (lưu phần tử $u$ có $d[u]$ nhỏ nhất)
  • Nút $H[i]$ có $d$ nút con là $H[d*i, \ldots, d*i + (d-1)]$.

Hai thủ tục quan trọng để duy trì cấu trúc Heap là UpHeapify DownHeapify.

UpHeapify( $u$):
    $v \leftarrow $ Parent( $u$)
    if $v \not= 0$ and $H[u] $ < $ H[v] $         $\ll u$ is not the root $\gg$
        swap $H[u] \leftrightarrow H[v]$
        UpHeapify($v$)

 

Parent( $u$):
    return $(u - u\mod d)/d$

 
Như vậy, thủ tục UpHeapify có thể thực hiện trong thời gian $O(\log_d(V))$ trong đó $\log_d(V)$ là chiều cao của cây Heap.

DownHeapify( $u$):
    $m \leftarrow d*u$
    for $i \leftarrow 1 $ to $d-1$
        $v \leftarrow d*u + i$
        if $H[v]$ < $H[m]$
            $m \leftarrow v$
    if $H[m]$ < $H[u]$
        swap $H[u] \leftrightarrow H[m]$
        DownHeapify($m$)

Như vậy, thủ tục DownHeapify có thể thực hiện trong thời gian $O(d\log_d(V))$

Để thưc hiện ExtractMin, ta sẽ lấy phần tử cuối cùng của mảng $H$ thay vào gốc và gọi DownHeapify với nút gốc. Để thưc hiện DecreaseKey của một nút $u$, ta sẽ giảm khóa của $u$ và gọi UpHeapify với $u$. Như vậy, ta có thể thực hiện (1) trong thời gian $O(d\log_d(V))$ và (2) trong $O(\log_d(V))$. Do đó, sử dụng Heap $d$-phân, thời gian thực hiện thuật toán Dijkstra là:

$O(Vd\log_d V) + \sum_{u\in V}d^{-}(u)\log_d V = O(Vd\log_d V + E\log_d V)\qquad (4)$

Để giá trị của biểu thức $(4)$ nhỏ nhất, ta chọn $d = \lfloor m/n \rfloor$. Như vậy, ta có:

Theorem 1: Sử dụng Heap $m/n$-phân, ta có thể thực thi thuật toán Dijkstra trong thời gian $O(m\log_{m/n}n)$.

 

Với đồ thị thưa $m = O(n)$, ta sẽ thu được thuật toán $O(n\log n)$. Với đồ thị dầy $m = O(n^2)$, ta sẽ thu được thuật toán $O(m)$. So với Fibonacci Heap thì thực thi Heap $m/n$-phân đơn giản hơn rất nhiều.

Thực thi phụ thuộc trọng số đầu vào

Giả sử trọng số của $G$ là các số nguyên và $C$ là trọng số lớn nhất trong tất cả các cạnh của $G$. Ta sẽ trình bày hai thuật toán khác nhau có thời gian phụ thuộc vào $C$.

Thuật toán $O(m + nC)$

Cách thực thi này được phát triển đầu tiên bởi Dial[2], và do đó còn được gọi là Dial's implementation. Do đường đi ngắn nhất từ $v$ tới một đỉnh $u$ bất kì có tối đa $n-1$ cạnh, ta có nhận xét sau:

Nhận xét: Khoảng cách ngắn nhất từ $v$ đến một đỉnh $u$ bất kì là một số nguyên trong tập $\{1,2,\ldots, C*(n-1)\}$

Ta sẽ thực thi một cấu trúc dữ liệu $B$ tương tự như Heap với hai thao tác hỗ trợ chính là ExtractMin DecreaseKey. Cấu trúc $B$ của chúng ta sẽ gồm một tập $C*(n-1)$ danh sách liên kết đôi (lý do ta chọn danh sách liên kết đôi là vì các thao tác: thêm, xóa, sửa một phần tử trong danh sách liên kết (khi có con trỏ tới phần tử đó) đều có thể thực hiện trong $O(1)$). Mỗi danh sách ta coi như một cái "giỏ" (bucket) để lưu trữ các đỉnh.

Giỏ thứ $i$ lưu các đỉnh $u$ có khoảng cách ước lượng $d[u] = i$

Ví dụ với hình dưới đây minh họa đồ thị (trọng số lớn nhất là $5$, hình chỉ thể hiện trọng số của các cạnh kề với đỉnh nguồn $a$) và tập các giỏ (thực ra là "xô" nhưng mình chưa tìm thấy hình cái giỏ nào đẹp cả :D) tại bước đầu tiên. Các số nhỏ màu đỏ ở dưới đáy mỗi giỏ là số thứ tự của giỏ.

bucket-example

Do ta chỉ có tất cả tối đa $n$ phần tử, phần lớn các giỏ sẽ rỗng. Để chèn một đỉnh $x$ vào giỏ, ta chỉ việc đưa đỉnh đó vào giỏ thứ $d[x]$, do đó ta có thể thực hiện trong thời gian $O(1)$. Ngoài ra, để thuận lợi cho thao tác ExtractMin, ta sẽ duy trì một con trỏ $\min$ để trỏ tới giỏ có thứ tự nhỏ nhất mà không rỗng $B_m$.

  • DecreaseKey: Nếu ta muốn giảm khóa $d[x]$ của nút $x$ xuống một giá trị $k$, ta chỉ việc chuyển $x$ sang giỏ thứ $k$. Sau khi giảm khóa của $x$, ta có thể phải cập nhật lại con trỏ $\min$. Toàn bộ các thao tác này có thể thực hiện trong thời gian $O(1)$.
  • ExtractMin: Nếu $B_m$ có ít nhất 2 phần tử, ta chỉ việc lấy một phần tử (ở đầu danh sách) ra khỏi $B_m$. Nếu $B_m$ có duy nhất 1 phần tử, sau khi lấy phần tử đó ra khỏi giỏ, ta phải cập nhật lại con trỏ $\min$. Ta cập nhật lại bằng cách bắt đầu từ $B_m$, duyệt các giỏ theo thứ tự chỉ số tăng dần cho đến khi ta tìm được một giỏ không rỗng và trỏ $\min$ tới giỏ đó. Việc khó nhất còn lại là phân tích xem thao tác cập nhật lại con trỏ min hết bao nhiều thời gian.

Giả mã:

DecreaseKeyBucketHeap($B[1,\ldots, (n-1)*C], v, k$):
    remove $v$ from the bucket containing $v$
    add $v$ to $B[k]$

 

ExtractMinBucketHeap($B[1,\ldots, (n-1)*C], \min$):
    $tmp \leftarrow$ an element in the bucket $B[\min]$
    remove $tmp$ from $B[\min]$
    if $B[\min] \not= \emptyset$
        return $tmp$
    else
        while $B[\min] \not= \emptyset$
            $\min \leftarrow \min + 1$

 
Phân tích thời gian cập nhật con trỏ $\min$: Để có thể phân tích được thời gian cập nhật con trỏ $\min$, chúng ta phải nhìn sâu hơn vào cấu trúc các giỏ trong mỗi bước của thuật toán. Gọi $M_i, m_i$ lần lượt là chỉ số lớn nhất và nhỏ nhất trong số các giỏ $B$ ở bước thứ $i$ của thuật toán mà $B[M_i] \not= \emptyset, B[m_i] \not= \emptyset$.

Bước khởi tạo (bước thứ 0) khi ta bắt đầu thuật toán, chỉ có $C$ cái giỏ là không rỗng do các cạnh có trọng số từ $\{1,2,\ldots, C\}$. Do đó, $M_0 - m_0 \leq C$. Ta có nhận xét sau:

Nhận xét: Ước lượng đường đi $d[x]$ của một đỉnh $x$ không tăng trong quá trình thực thi thuật toán Dijkstra.

Dựa vào nhận xét trên, ta chứng minh bổ đề sau:

Lemma 1: Tại bất kì bước thứ $i$ nào của thuật toán, $M_i - m_i \leq C$

 

Chứng minh Ta chứng minh bằng quy nạp. $i = 0$, bổ đề đúng như đã thảo luận ở trên. Gỉa sử $M_{i-1} - m_{i-1} \leq C$. Khi đỉnh có nhãn nhỏ nhất, gọi là $v$, tại bước thứ $i-1$ đã được thêm vào cây đường đi ngắn nhất, một số đỉnh khác có thể được thêm vào giỏ $B$ và một số đỉnh sẽ được cập nhật lại nhãn. Cho dù là thêm vào hay cập nhật lại, nhãn của đỉnh đó, gọi là $x$, sẽ thỏa mãn $d[x] \leq d[v] + C $ và $d[x] \geq d[v]$. Chú ý $d[v] = m_{i-1}$. Do đó, nhãn lớn nhất tại bước thứ $i$ sẽ là $M_i = \max(M_{i-1}, m_{i-1} + C)$ và nhãn nhỏ nhất tại bước thứ $i$ là $m_{i} \geq m_{i-1}$. Do đó, ta có:

$\begin{array}{lcl} M_i - m_{i} & \leq & M_{i} - m_{i-1} \\ & = & \max(M_{i-1}, m_{i-1} + C) - m_{i-1} \\ & = & \max(M[i-1] - m_{i-1}, C) = C \qquad (5) \end{array}$

Do đó, bổ đề đúng.


Từ bổ đề trên ta suy ra, để cập nhật con trỏ $\min$, ta chỉ cần duyệt qua $C$ bước là sẽ tìm được giá trị cập nhật. Do đó, tổng thời gian thực thi của thuật toán là:

$O(nC + \sum_{u\in V}d^{-}(u)) = O(nC + m)\qquad (6)$

Theorem 2: Cách thực thi thuật toán Dijkstra của Dial có thời gian $O(m + nC)$.

 

Giảm bộ nhớ Cách thực thi của Dial sử dụng $nC$ cái giỏ và theo Lemma 1, hầu hết các giỏ là rỗng (chỉ có $C+1$ giỏ là không rỗng). Do đó, thay vì sử dụng $nC$ cái giỏ, ta sẽ chỉ sử dụng $C+1$ cái giỏ. Các giỏ này sẽ được liên kết với nhau theo kiểu vòng (giống danh sách liên kết vòng -- circular linked list). Giỏ thứ $i$ sẽ lưu các đỉnh $x$ có $d[x] \equiv i \mod C+1$. Ta sẽ sử dụng một con trỏ để trỏ đến cái giỏ chứa các đỉnh có khoảng cách ngắn nhất (không nhất thiết là giỏ có chỉ số $0$). Xem hình vẽ dưới đây. Bằng cách này ta có thể giảm bộ nhớ xuống còn $O(n + C)$.

circular-bucket

Thuật toán $O(m + n\log(nC))$ sử dụng Radix Heap

Thuật toán này được đề xuất bởi Ahuja, Mehlhorn, Orlin và Tarjan [4]. Trong thuật toán này, thay vì sử dụng $(n-1)*C$ cái giỏ (mỗi giỏ vẫn là một danh sách liên kết đôi), ta sẽ chỉ sử dụng $\log (nC)$ cái giỏ. Thay vì mỗi cái giỏ chỉ chứa các đỉnh có chung một giá trị ước lượng khoảng cách như trong Dial's implementation, ta cho phép mỗi giỏ chứa các đỉnh có giá trị ước lượng khoảng cách cùng trong một khoảng.

Ví dụ trong Dial's implementation, giỏ $B[3]$ sẽ chứa các đỉnh $v$ có $d[v = 3]$. Tuy nhiên ở đây, giỏ $B[3]$ có thể chứa các đỉnh $v$ có $4 \leq d[v] \leq 7$.

Ta định nghĩa độ rộng (width) của một giỏ là độ rộng của khoảng giá trị mà giỏ đó cho phép. Ở đây ta nhấn mạnh độ dài. Ví dụ nếu $B[3]$ chứa các đỉnh $v$ có $4 \leq d[v] \leq 7$ thì độ rộng của $B[3]$ là $4$. Mỗi giỏ ta sẽ sử dụng có độ rộng như sau:

Giỏ $B[i]$ có độ rộng là $2^{i-1}$

Trong đó, ta quy ước, giỏ $B[0]$ có độ rộng là $1$. Theo như quy ước trên, giỏ $B[1]$ có độ rộng là $1$, giỏ $B[2]$ có độ rộng là $2$, giỏ $B[3]$ có độ rộng là $4$, .... Do đó, ngoại trừ hai giỏ đầu tiên, giỏ $B[i]$ có độ rộng bằng 2 lần giỏ $B[i-1]$.

Nên nhớ ở trên ta chỉ quy ước độ rộng của giỏ, chưa phải khoảng giá trị. Hai khoảng giá trị khác nhau vẫn có thể có cùng độ rộng. Ví dụ $[3,7]$ và $[6,10]$ là hai khoảng khác nhau có cùng độ rộng. Điểm đặc biệt trong cách thực thi này là khoảng giá trị của các giỏ sẽ thay đổi theo từng bước của thuật toán.

Ban đầu, giỏ $B[i]$ sẽ có khoảng giá trị từ $2^{i-1}$ đến $2^i-1$.

Quy ước, $B[0]$ có khoảng giá trị là $[0,0]$. Như vậy, $B[1]$ có khoảng giá trị là $[1,1]$, $B[2]$ có khoảng giá trị là $[2,3]$, $B[3]$ có khoảng giá trị là $[4,7]$...., $B[\log(n*C)]$ có khoảng giá trị là $[n*C/2,n*C - 1]$. Do đó, ta chỉ cần $\log (n*C)$ cái giỏ vì nhãn của các đỉnh trong mọi trường hợp đều không quá $(n-1)*C \leq n*C-1$. Tập các giỏ này ta gọi là một Radix Heap. Nhắc lại: khoảng giá trị của các giỏ sẽ thay đổi theo từng bước của thuật toán.

Để hỗ trợ thao tác ExtractMin, ta cũng lưu một con trỏ $\min$ để trỏ tới giỏ có chỉ số nhỏ nhất và không rỗng. Ta sẽ thực hiện hai thao tác của Heap như sau:

  • DecreaseKeyTương tự như trên, để giảm một khóa ta cũng chỉ việc lấy đỉnh $v$ từ giỏ hiện tại chứa $v$ (gọi là giỏ $i$) đến một giỏ mới $k$ nếu như giá trị khóa mới $k$ vượt ra khỏi khoảng giá trị ước lượng của giỏ đang chứa $v$.
  • ExtractMin Thao tác này phức tạp hơn một chút và khoảng giá trị của các giỏ có thể sẽ thay đổi sau thao tác này. Giả sử con trỏ $\min$ đang trỏ tới giỏ $B[i]$ với $i > 1$. Ta chỉ quan tâm khi $i > 1$ vì các giỏ $B[0], B[1]$ chỉ có độ rộng là $1$ (các phần tử trong giỏ đều có ước lượng bằng nhau), do đó lấy min chỉ đơn giản là lấy ra một phần tử bất kì. Do:

    $2^{i-1} = 1 + 1 + 2 + 4 +... + 2^{i-2}$

    Ta suy ra độ rộng của $B[i] = 2^{i-1}$ và bằng tổng độ rộng của tất cả các giỏ trước đó cộng lại. Ngoài ra, chú ý là khi $B[i]$ là giỏ chứa phần tử có ước lượng nhỏ nhất, thì các giỏ trước đó $B[0], B[1], ..., B[i-1]$ đều rỗng. Gọi $x$ là phần tử có ước lượng $d[x]$ là nhỏ nhất trong giỏ $B[i]$. Ta sẽ thực hiện:

    Trước khi lấy ra phần tử nhỏ nhất, việc ta sẽ làm là chuyển tất cả các phần tử của giỏ $B[i]$ xuống tất cả các giỏ có chỉ số thấp hơn. Phần tử nhỏ nhất $x$ sẽ được chuyên tới giỏ $B[0]$ (do đó, coi như giỏ này giờ có khoảng là $[d[x], d[x]]$). Các phần tử có ước lượng $d[x]+1$ sẽ được chuyến xuống giỏ $B[1]$ (do đó, coi như giỏ này giờ có khoảng là $[d[x]+1, d[x]+1]$), các phần tử có ước lượng từ $d[x]+2$ tới $d[x] + 3$ sẽ được chuyến xuống giỏ $B[2]$, các phần tử có ước lượng từ $d[x]+4$ tới $d[x] + 7$ sẽ được chuyến xuống giỏ $B[3]$, ...., các phần tử có ước lượng từ $d[x]+2^{j-1}$ tới $d[x] + 2^{j}-1$ sẽ được chuyến xuống giỏ $B[j]$....

    Sau khi chuyển hết, ta sẽ thực hiện lấy một phần tử ra khỏi $B[0]$ (giỏ này tại sao không rỗng?) và thêm nó vào cây đường đi ngắn nhất.

Phân tích thời gian: Việc khó nhất giờ là phân tích thời gian. Cập nhật khóa (thao tác 2) chỉ mất thời gian $O(1)$. Mỗi lần thực hiện thao tác ExtractMin, hoặc mất thời gian $O(1)$ (nếu $B[0], B[1]$ không rỗng), hoặc mất thời gian tuyến tính với số phần tử trong giỏ $B[i]$ (nếu cả hai giỏ nhỏ nhất đều rỗng). Trong trường hợp sau, ta sẽ chuyển các phần tử trong giỏ $B[i]$ xuống giỏ thấp hơn. Do đó, tổng thời gian của các thao tác ExtractMin có cùng tiệm cận với tổng thời gian chuyển các đỉnh xuống các giỏ thấp hơn. Do ta chỉ có $\log (n*C)$ giỏ, mỗi giỏ sẽ được chuyển tối đa $\log (n*C)$ lần (vì ta không bao giờ chuyển một đỉnh từ giỏ có chỉ số thấp lên giỏ có chỉ số cao). Do đó, tổng thời gian chuyển các đỉnh sẽ là $O(n\log (n*C))$. Do đó, ta có:

Theorem 3: Cách thực thi thuật toán Dijkstra sử dụng Radix Heap có thời gian $O(m + n\log(nC))$.

Dựa vào Lemma 1, ta có thể giảm bộ nhớ của thực thi này xuống còn $O(n + \log C)$ thay vì $O(n + \log nC)$.

Final Remark: Johnson [5] đề xuất một cấu trúc Heap khác cho phép thực thi thuật toán Dijkstra trong thời gian $O(m \log \log C)$. Ahuja, Mehlhorn, Orlin và Tarjan [4] đề xuất kết hợp áp dụng Fibonacci Heap bên trong Radix Heap, giảm thời gian thực thi xuống còn $O( m + n \sqrt{\log C)}$. Đây là một trong số những cách thực thi nhanh nhất mà mình biết.

Tham khảo

[1] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., Upper Saddle River, NJ, USA.
[2] Dial, Robert B. Algorithm 360: Shortest-path forest with topological ordering [H]. Communications of the ACM 12.11 (1969): 632-633.
[3] Johnson, Donald B. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM (JACM) 24.1 (1977): 1-13.
[4] Ahuja, R. K., Mehlhorn, K., Orlin, J., & Tarjan, R. E. Faster algorithms for the shortest path problem. Journal of the ACM (JACM), 37.2 (1990): 213-223.
[5] Johnson, D. B. Efficient special-purpose priority queues. Proceedings of the 15th Annual Allerton Conference on Communications, Control, and Computing. 1977.

Tags: , , , , , , , ,

« Older entries