Demo Dijkstra tìm đường đi ngắn nhất

Thuật toán Dijkstra tìm đường đi ngắn nhất 

          Năm 1959 E. W. Dijkstra đưa ra một thuật toán rất hiệu quả để giải bài toán đường đi ngắn nhất. Thuật toán thực hiện việc gán và giảm giá trị của nhãn  l(i)  tại mỗi đỉnh   i

của đồ thị  G  như sau:

 1.  Với đỉnh xuất phát  a,  gán nhãn  l(a) := 0.

2.  Nếu có cạnh  (i,j)  mà đỉnh  i  đã được gán nhãn và đỉnh  j   chưa được gán nhãn hoặc đỉnh  j  đã được gán nhãn nhưng  l(i) + c(i,j) < l(j)  thì giảm nhãn

l(j)  :=  l(i) + c(i,j).

3.  Lặp lại bước 2. cho đến khi không gán hoặc giảm nhãn được nữa.

" Tại mỗi đỉnh  b giá trị nhãn l(b)  cuối cùng (nếu có) chính là độ dài của đường đi ngắn nhất từ đỉnh  a  đến đỉnh  b."

Chứng minh:

           Sau khi đã thực hiện xong thuật toán trên, nếu giá trị nhãn l(b) xác định thì ta có đường đi từ đỉnh  a  tới đỉnh  b.  

Ta khôi phục đường đi từ  a  đến  b  như sau:

Xuất phát từ đỉnh  b,  tìm cạnh có đỉnh cuối là  b  và đỉnh đầu là  i  sao cho:

     l(i) + c(i,b)  =  l(b).

Đỉnh  i  như thế chắc chắn phải tồn tại vì xảy ra đẳng thức ở lần gán hoặc giảm giá ị nhãn l(j)  cuối cùng. Cứ tiếp tục như thế cho đến khi gặp đỉnh  a. 

Giả sử ta nhận được dãy các cạnh:

            (a, a1) , (a1, a2) ,  ...  , (ak-1, b)  

   mà trên đó:     l(a)    +  c(a,a1)     =  l(a1)

   l(a1)   +  c(a1,a2)   =  l(a2)

      .. . ..  . . . .. .. .. . . .. .. . . 

   l(ak-1) + c(ak-1, b)  =  l(b).

Cộng từng vế và khử các giá trị chung ở cả hai vế ta có:  

c(a,a1) + c(a1,a2) + ... + c(ak-1,b)  = l(b).

Vậy giá trị nhãn l(b)  chính là độ dài đường đi nói trên. 

Bất kỳ đường đi nào khác từ đỉnh  a   đến đỉnh  b   cũng có các hệ thức tương tựnhưng có dấu ≥. 

Vậy nhãn l(b) là độ dài của đường đi ngắn nhất.          

      Độ dài đường đi ngắn nhất từ đỉnh  a  đến đỉnh  b  là 5.

  Để đơn giản việc tính toán, ta xây dựng ma trận trọng số  C :

Khi đó, thuật toán Dijkstra được trình bày chi tiết hơn như sau:

procedure  DIJKSTRA(a)  ;

  begin

Bước 1:   for   j ∈ V   do

     begin

   L[j]  :=  C[a, j]  ;  Truoc[j]  :=  a 

     end ;

  T  :=  V \ {a} ;

Bước 2:  while  T ≠ ∅  do

     begin

   chọn đỉnh  i ∈ T mà  L[i] = min {L[j] ⏐ j ∈T }  ;

    T  :=  T \ {i}  ;

    for    j ∈ T   do

       if   L[j]  >  L[i]  + C[i, j]   then

      begin   

      L[j]  :=  L[i]  + C[i, j]  ;

      Truoc[j]  :=  i ;

   end  ;

     end ;

   end ;  

Biến mảng "Truoc" dùng để khôi phục đường đi.

Đánh Giá Giải Thuật.

Bước 1: tốn chi phí O(n).

Bước 2: tốn chi phí O(n²).

Số vòng lặp tối đa là n.

Cố định nhãn tốn chi phí O(n) cho việc tìm kiếm.

Sửa nhãn tốn chi phí O(n).

àBài toán có độ phức tạp trung bình O(n²) trên các đồ thị liên thông.