Cách tìm "Tuyến đường" của tất cả các đường dẫn ngắn nhất của cặp với thuật toán Floyd-Warshall trong C#

Giới thiệu

Trong bài đăng trước , chúng ta đã thấy cách giải quyết bài toán đường đi ngắn nhất cho mọi cặp bằng thuật toán Floyd-Warshall . Chúng ta cũng đã khám phá một số cách để cải thiện hiệu suất của thuật toán bằng cách sử dụng song song và vectơ hóa.

Tuy nhiên, nếu bạn nghĩ về kết quả của thuật toán Floyd-Warshall, bạn sẽ nhanh chóng nhận ra khoảnh khắc thú vị - chúng ta biết khoảng cách (giá trị của đường dẫn ngắn nhất) giữa các đỉnh trong đồ thị nhưng chúng ta không biết "tuyến đường" tức là chúng ta không biết những đỉnh nào góp phần tạo nên mỗi đường dẫn ngắn nhất và chúng ta không thể xây dựng lại các "tuyến đường" này từ kết quả chúng ta có.

Trong bài đăng này, tôi mời bạn tham gia cùng tôi và mở rộng thuật toán Floyd-Warshall. Lần này, chúng ta sẽ đảm bảo có thể tính toán khoảng cách và xây dựng lại "tuyến đường".

Một chút lý thuyết đã biết…

Trước khi tìm hiểu sâu hơn về mã và điểm chuẩn, chúng ta hãy xem lại lý thuyết về cách thức hoạt động của thuật toán Floyd-Warshall.

Sau đây là mô tả bằng văn bản của thuật toán:

1. Chúng tôi bắt đầu bằng cách biểu diễn một đồ thị ( G ) có kích thước N dưới dạng ma trận ( W ) có kích thước N x N trong đó mỗi ô W[i,j] chứa trọng số của một cạnh từ đỉnh i đến đỉnh j (xem Hình 1). Trong trường hợp không có cạnh nào giữa các đỉnh, ô được đặt thành giá trị NO_EDGE đặc biệt (được hiển thị dưới dạng các ô tối trong Hình 1).

   
   

2. Từ bây giờ, chúng ta nói – W[i,j] chứa khoảng cách giữa các đỉnh i và j .

   
   

3. Tiếp theo, chúng ta lấy một đỉnh k và lặp qua tất cả các cặp đỉnh W[i,j] để kiểm tra xem khoảng cách i ⭢ k ⭢ j có nhỏ hơn khoảng cách hiện đã biết giữa i và j hay không.

   
   

4. Giá trị nhỏ nhất được lưu trữ trong W[i,j] và bước #3 được lặp lại cho k tiếp theo cho đến khi tất cả các đỉnh của G được sử dụng làm k .

Sau đây là mã giả:

 algorithm FloydWarshall(W) do for k = 0 to N - 1 do for i = 0 to N - 1 do for j = 0 to N - 1 do W[i,j] = min(W[i,j], W[i,k] + W[k,j]) end for end for end for end algorithm

Khi thực hiện xong, mỗi ô W[i,j] của ma trận W sẽ chứa khoảng cách của đường dẫn ngắn nhất giữa các đỉnh i và j hoặc giá trị NO_EDGE nếu không có đường dẫn nào giữa chúng.

Như tôi đã đề cập ở phần đầu – chỉ có thông tin này khiến việc tái tạo các tuyến đường giữa các đỉnh này trở nên bất khả thi. Vậy… chúng ta nên làm gì để có thể tái tạo các tuyến đường này?

Vâng… điều này có vẻ hiển nhiên nhưng… chúng ta cần thu thập thêm dữ liệu!

… Một chút lý thuyết tương tự nhưng từ góc nhìn khác

Bản chất của thuật toán Floyd-Warshall là một ngăn có khoảng cách đã biết W[i,j] với khoảng cách có thể là đường dẫn mới từ i đến j qua đỉnh trung gian k .

Tôi tập trung nhiều sự chú ý vào chi tiết này vì đây là chìa khóa để chúng ta có thể bảo toàn thông tin tuyến đường. Hãy lấy đồ thị trước gồm 5 đỉnh (xem Hình 2) và thực hiện thuật toán Floyd-Warshall trên đó.

Ban đầu, chúng ta biết về tất cả các cạnh của đồ thị, điều này cung cấp cho chúng ta các đường dẫn sau: 0 ⭢ 1 :2 , 0 ⭢ 4 1 ⭢ 3 :1 0 ⭢ 4 :10 , 1 ⭢ 2 ⭢ 4 :1 , 2 ⭢ 4 :1 , 3 ⭢ 2 :1 và 3 ⭢ 4 :3 .

Chúng ta cũng biết rằng không có cạnh nào dẫn đến đỉnh 0 , do đó việc thực thi thuật toán cho k = 0 là vô nghĩa. Một điều hiển nhiên nữa là có một cạnh duy nhất ( 0 ⭢ 1 ) dẫn từ đỉnh 0 đến đỉnh 1 , điều này cũng khiến cho việc thực thi tất cả i != 0 ( i là "from" ở đây) trở nên khá vô nghĩa và vì đỉnh 1 có các cạnh có 2 và 4 , nên việc thực thi thuật toán cho bất kỳ j nào không phải là 2 hoặc 4 ( j là "to" ở đây) cũng không có ý nghĩa gì.

Đó là lý do tại sao bước đầu tiên của chúng ta sẽ là thực hiện thuật toán cho k = 1 , i = 0 và j = 2,4 .

Chúng tôi đã tìm thấy hai đường dẫn: một đường dẫn mới ( 0 ⭢ 1 ⭢ 2 ) và một lối tắt ( 0 ⭢ 1 ⭢ 4 ). Cả hai đều đi qua đỉnh 1 . Nếu chúng ta không lưu trữ thông tin này (thực tế là chúng ta đã đến 2 và 4 thông qua 1 ) ở đâu đó ngay bây giờ, nó sẽ bị mất mãi mãi (và điều đó hoàn toàn trái ngược với những gì chúng ta mong muốn).

Vậy chúng ta nên làm gì? Chúng ta sẽ cập nhật ma trận W với các giá trị mới (xem Hình 3a) và cũng lưu trữ giá trị của k (là k = 1 ) trong các ô R[0,2] và R[0,4] của ma trận R mới có cùng kích thước với ma trận W nhưng được khởi tạo bằng các giá trị NO_EDGE (xem Hình 3b).

Hiện tại, đừng tập trung vào ma trận R chính xác là gì. Chúng ta hãy tiếp tục và thực hiện thuật toán cho k = 2 tiếp theo.

Ở đây, chúng ta sẽ thực hiện cùng một phân tích (để hiểu những kết hợp nào có ý nghĩa để thực hiện) như chúng ta đã làm với k = 1, nhưng lần này, chúng ta sẽ sử dụng ma trận W thay vì đồ thị G Hãy xem ma trận W , đặc biệt là ở cột số 2 và hàng số 2 (Hình 4).

Ở đây bạn có thể thấy, có hai đường dẫn đến đỉnh 2 từ đỉnh 0 và từ đỉnh 1 (cột #2), và hai đường dẫn từ đỉnh 2 đến đỉnh 3 và đến đỉnh 4 (hàng #2). Biết được điều đó, việc thực hiện thuật toán chỉ có ý nghĩa đối với các tổ hợp k = 2 , i = 0,1 và j = 3,4 .

Như chúng tôi đã thực hiện trước đây, chúng tôi đang cập nhật các ô W[0,3] , W[0,4] , W[1,3] , W[1,4] với các khoảng cách mới và các ô R[0,3] , R[0,4] , R[1,3] và R[1,4] với k = 2 (xem Hình 5).

Chỉ còn k = 3 để xử lý (vì không có cạnh nào dẫn từ đỉnh 4 đến bất kỳ đỉnh nào khác trong đồ thị).

Một lần nữa, chúng ta hãy xem xét ma trận W (Hình 6).

Theo ma trận W , có ba đường dẫn đến đỉnh 3 từ các đỉnh 0 , 1 và 2 (cột #3), và có một đường dẫn từ đỉnh 3 đến đỉnh 4 (hàng #3). Do đó, chúng ta có các đường dẫn sau để xử lý:

Đây là lần lặp lại cuối cùng của thuật toán. Tất cả những gì còn lại là cập nhật các ô W[0,4] , W[1,4] , W[2,4] với khoảng cách mới và đặt các ô R[0,4] , R[1,4] , R[2,4] thành 3 .

Đây là kết quả cuối cùng của thuật toán (Hình 7).

Như chúng ta đã biết từ bài đăng trước , ma trận W hiện chứa tất cả các cặp đường đi ngắn nhất trong đồ thị G Nhưng những gì được lưu trữ bên trong ma trận R ?

Trở về nhà

Mỗi lần chúng ta tìm thấy một đường đi ngắn nhất mới, chúng ta đang cập nhật ô tương ứng của ma trận R với giá trị hiện tại của k . Mặc dù lúc đầu, hành động này có vẻ bí ẩn nhưng nó có ý nghĩa rất đơn giản – chúng ta đang lưu trữ đỉnh, từ đó chúng ta đến được đỉnh đích: i ⭢ k ⭢ j (ở đây chúng ta đang đến j trực tiếp từ k ).

Khoảnh khắc này rất quan trọng. Bởi vì biết được đỉnh mà chúng ta đến từ đó cho phép chúng ta xây dựng lại lộ trình bằng cách di chuyển ngược lại (giống như một con tôm hùm) từ đỉnh j (chữ “đến”) đến đỉnh i (chữ “từ”).

Sau đây là mô tả bằng văn bản về thuật toán xây dựng lại tuyến đường từ i đến j :

1. Chuẩn bị mảng động rỗng X
2. Bắt đầu bằng cách đọc giá trị z từ ô R[i,j] .
3. Nếu z là NO_EDGE thì tuyến đường từ i đến j được tìm thấy và chúng ta nên tiến hành bước #7.
4. Thêm z vào trước mảng động X
5. Đọc giá trị của ô R[i,z] vào z .
6. Lặp lại các bước #3, #4 và #5 cho đến khi đạt được điều kiện thoát ở #3.
7. Thêm i vào trước X.
8. Thêm j vào X
9. Bây giờ mảng động X chứa tuyến đường từ i đến j .

Trong mã giả, nó thậm chí còn trông đơn giản hơn:

 algorithm RebuildRoute(i, j, R) x = array() z = R[i,j] while (z ne NO_EDGE) do x.prepend(z) z = R[i,z] end while x.prepend(i) x.append(j) return x end algorithm

Hãy thử trên đồ thị G của chúng ta và xây dựng lại một lộ trình từ đỉnh 0 đến đỉnh 4 (xem Hình 8).

Sau đây là mô tả bằng văn bản về hình ảnh minh họa trên:

1. Chúng ta bắt đầu bằng cách đọc giá trị từ R[0,4] , kết quả là 3 . Theo thuật toán, điều này có nghĩa là tuyến đường đi đến đỉnh 4 từ đỉnh 3 (hiển thị bằng MÀU XANH LAM).

   
   

2. Vì giá trị của R[0,4] không phải là NO_EDGE , chúng ta tiến hành và đọc giá trị của R[0,3] , kết quả là 2 (hiển thị bằng màu XANH LÁ).

   
   

3. Một lần nữa, vì giá trị của R[0,3] không phải là NO_EDGE , chúng ta tiến hành và đọc giá trị của R[0,2] , kết quả là 1 (hiển thị bằng MÀU ĐỎ).

   
   

4. Cuối cùng, chúng ta đọc giá trị R[0,1] , dẫn đến giá trị NO_EDGE , nghĩa là không còn đỉnh nào nữa ngoại trừ 0 và 4 góp phần vào tuyến đường. Do đó, tuyến đường kết quả là: 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 mà nếu bạn nhìn vào đồ thị thì thực sự tương ứng với đường đi ngắn nhất từ đỉnh 0 đến đỉnh 4 .

Một độc giả chu đáo có thể hỏi:

Đây là một câu hỏi rất hay. Chúng tôi chắc chắn vì chúng tôi cập nhật ma trận R với một giá trị mới khi chúng tôi cập nhật giá trị đường dẫn ngắn nhất trong ma trận W Vì vậy, cuối cùng, mỗi hàng của ma trận R chứa dữ liệu liên quan đến đường dẫn ngắn nhất. Không nhiều hơn, không ít hơn.

Bây giờ chúng ta đã hoàn thành phần lý thuyết, đã đến lúc thực hiện.

Triển khai trong C#

Trong bài đăng trước , bên cạnh việc triển khai phiên bản gốc của thuật toán Floyd-Warshall, chúng tôi cũng đã tích hợp nhiều tối ưu hóa khác nhau: hỗ trợ đồ thị thưa thớt, song song và vectơ hóa, và cuối cùng, chúng tôi cũng kết hợp tất cả chúng lại.

Không có lý do gì để lặp lại tất cả những điều này ngày hôm nay. Tuy nhiên, tôi muốn chỉ cho bạn cách tích hợp ghi nhớ tuyến đường vào các phiên bản gốc và phiên bản vector hóa (có hỗ trợ đồ thị thưa thớt) của thuật toán.

Tích hợp vào thuật toán gốc

Có thể khó tin nhưng để tích hợp tính năng ghi nhớ lộ trình vào phiên bản gốc của thuật toán, tất cả những gì chúng ta cần làm là:

1. Mở rộng chữ ký hàm để bao gồm ma trận R dưới dạng tham số riêng biệt – int[] routes .

   
   

2. Lưu k vào routes mỗi khi đường dẫn ngắn nhất được thay đổi (dòng: 2 và 14).

Vậy thôi. Chỉ cần một dòng rưỡi mã:

 public void BaselineWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { for (var i = 0; i < sz; ++i) { for (var j = 0; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } }

Tích hợp vào thuật toán vector hóa

Việc tích hợp vào phiên bản vector hóa (có hỗ trợ đồ thị thưa thớt) cần nhiều nỗ lực hơn để hoàn thành, tuy nhiên, các bước khái niệm thì giống nhau:

1. Mở rộng chữ ký hàm để bao gồm ma trận R dưới dạng tham số riêng biệt – int[] routes .

   
   

2. Ở mỗi lần lặp lại, khởi tạo một vectơ mới gồm k giá trị (dòng: 6).

   
   

3. Lưu k giá trị vector vào routes mỗi khi đường dẫn ngắn nhất thay đổi (dòng: 31-32).

   
   

4. Cập nhật phần không được vector hóa của thuật toán theo cùng cách chúng ta cập nhật thuật toán gốc (dòng: 41).

 public void SpartialVectorOptimisationsWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { var k_vec = new Vector<int>(k); for (var i = 0; i < sz; ++i) { if (matrix[i * sz + k] == Constants.NO_EDGE) { continue; } var ik_vec = new Vector<int>(matrix[i * sz + k]); var j = 0; for (; j < sz - Vector<int>.Count; j += Vector<int>.Count) { var ij_vec = new Vector<int>(matrix, i * sz + j); var ikj_vec = new Vector<int>(matrix, k * sz + j) + ik_vec; var lt_vec = Vector.LessThan(ij_vec, ikj_vec); if (lt_vec == new Vector<int>(-1)) { continue; } var r_vec = Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec); r_vec.CopyTo(matrix, i * sz + j); var ro_vec = new Vector<int>(routes, i * sz + j); var rk_vec = Vector.ConditionalSelect(lt_vec, ro_vec, k_vec); rk_vec.CopyTo(routes, i * sz + j); } for (; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } }

Đánh giá chuẩn

Thu thập thông tin tuyến đường có vẻ hợp lý vì… tại sao không? Đặc biệt là khi nó dễ dàng tích hợp vào các thuật toán hiện có. Tuy nhiên, hãy xem việc tích hợp nó theo mặc định có thực tế không.

Sau đây là hai bộ chuẩn: có và không có (cả hai đều thực hiện phiên bản gốc và phiên bản vectơ của thuật toán). Tất cả các chuẩn đều được thực hiện bằng BenchmarkDotNet v0.13.1 (.NET 6.0.4 x64) trên máy được trang bị bộ xử lý Intel Core i5-6200U CPU 2,30 GHz (Skylake) và chạy Windows 10.

Tất cả các thí nghiệm đều được thực hiện trên tập đồ thị được xác định trước đã sử dụng trong bài đăng trước : 300, 600, 1200, 2400 và 4800 đỉnh.

Dưới đây là kết quả chuẩn trong đó các phương thức Baseline và BaselineWithRoutes tương ứng với phiên bản gốc của thuật toán và các phương thức SpartialVectorOptimisations và SpartialVectorOptimisationsWithRoutes tương ứng với phiên bản thuật toán được vector hóa (có hỗ trợ đồ thị thưa thớt).

Kết quả chuẩn không dễ để diễn giải. Nếu bạn xem xét kỹ hơn, bạn sẽ thấy sự kết hợp khi việc thu thập tuyến đường thực sự khiến thuật toán chạy nhanh hơn hoặc không có bất kỳ tác động đáng kể nào.

Điều này có vẻ rất khó hiểu (và nếu đúng như vậy – tôi thực sự khuyên bạn nên nghe chương trình này với Denis Bakhvalov và Andrey Akinshin để hiểu rõ hơn những điều khó khăn có thể ảnh hưởng đến phép đo). Quan điểm tốt nhất của tôi ở đây là hành vi “khó hiểu” là do hiệu suất bộ đệm CPU tuyệt vời (vì đồ thị không đủ lớn để bão hòa bộ đệm). Một phần, lý thuyết này dựa trên mẫu “ đậm ” mà chúng ta có thể thấy sự suy giảm đáng kể trên đồ thị lớn nhất. Tuy nhiên, tôi đã không xác minh điều đó.

Nhìn chung, điểm chuẩn cho thấy rằng nếu chúng ta không nói về các tình huống hiệu suất cực cao và đồ thị khổng lồ thì việc tích hợp ghi nhớ tuyến đường vào cả hai thuật toán theo mặc định là ổn (nhưng hãy nhớ rằng, điều này sẽ làm tăng gấp đôi mức sử dụng bộ nhớ vì chúng ta cần phân bổ hai ma trận W và R thay vì một).

Việc duy nhất còn lại là triển khai thuật toán xây dựng lại tuyến đường.

Triển khai thuật toán xây dựng lại tuyến đường

Việc triển khai các thuật toán xây dựng lại tuyến đường trong C# rất đơn giản và gần như phản ánh hoàn toàn mã giả đã trình bày trước đó (chúng tôi sử dụng LinkedList<T> để biểu diễn mảng động):

 public static IEnumerable<int> RebuildWithLinkedList( int[] routes, int sz, int i, int j) { var x = new LinkedList<int>(); var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x.AddFirst(z); z = routes[i * sz + z]; } x.AddFirst(i); x.AddLast(j); return x; }

Thuật toán trên không hoàn hảo và chắc chắn có thể được cải thiện. Cải tiến đơn giản nhất mà chúng ta có thể thực hiện là phân bổ trước một mảng có kích thước sz và điền vào theo thứ tự ngược lại:

 public static IEnumerable<int> RebuildWithArray( int[] routes, int sz, int i, int j) { var x = new int[sz]; var y = sz - 1; // Fill array from the end x[y--] = j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x[y--] = z; z = routes[i * sz + z]; } x[y] = i; // Create an array segment from 'y' to the end of the array // // This is required because 'sz' (and therefore length of the array x) // equals to the number of vertices in the graph // // So, in cases when route doesn't span through // all vertices - we need return a segment of the array return new ArraySegment<int>(x, y, sz - y); }

Trong khi "tối ưu hóa" này làm giảm số lần phân bổ xuống còn một, nó không nhất thiết làm cho thuật toán "nhanh hơn" hoặc "phân bổ ít bộ nhớ hơn" so với thuật toán trước đó. Vấn đề ở đây là nếu chúng ta cần có một tuyến đường được sắp xếp từ i đến j , chúng ta sẽ luôn phải "đảo ngược" dữ liệu mà chúng ta lấy được từ ma trận R và không có cách nào để thoát khỏi nó.

Nhưng nếu chúng ta có thể trình bày dữ liệu theo thứ tự ngược lại, thì chúng ta có thể sử dụng LINQ và tránh mọi phân bổ không cần thiết:

 public static IEnumerable<int> RebuildWithReverseYield( int[] routes, int sz, int i, int j) { yield return j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { yield return z; z = routes[i * sz + z]; } yield return i; }

Có thể có nhiều biến thể hơn nữa về cách mã này có thể được "thay đổi" hoặc "cải thiện". Điều quan trọng ở đây là phải nhớ - bất kỳ "thay đổi" nào cũng có nhược điểm về mặt bộ nhớ hoặc chu kỳ CPU.

Hãy thoải mái thử nghiệm! Khả năng là gần như vô hạn!

Phần kết luận

Trong bài đăng này, chúng tôi đã đi sâu vào lý thuyết đằng sau thuật toán Floyd-Warshall và đã mở rộng nó với khả năng ghi nhớ các "tuyến đường" ngắn nhất. Sau đó, chúng tôi đã cập nhật các triển khai C# (bản gốc và vector hóa) từ bài đăng trước . Cuối cùng, chúng tôi đã triển khai một số phiên bản của thuật toán để xây dựng lại các "tuyến đường".

Chúng tôi đã nhắc lại rất nhiều lần, nhưng đồng thời, tôi hy vọng bạn đã tìm thấy điều gì đó mới mẻ và thú vị trong bài này. Đây không phải là kết thúc của bài toán đường đi ngắn nhất cho mọi cặp. Đây chỉ là sự khởi đầu.

Tôi hy vọng bạn thích bài đọc này và hẹn gặp lại bạn vào lần sau!