Giới thiệu Trong , 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 . 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. bài đăng trước thuật toán Floyd-Warshall 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: Chúng tôi bắt đầu bằng cách biểu diễn một đồ thị ( ) có kích thước dưới dạng ma trận ( ) có kích thước trong đó mỗi ô chứa trọng số của một cạnh từ đỉnh đến đỉnh (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ị đặc biệt (được hiển thị dưới dạng các ô tối trong Hình 1). G N W N x N W[i,j] i j NO_EDGE Từ bây giờ, chúng ta nói – chứa khoảng cách giữa các đỉnh và . W[i,j] i j Tiếp theo, chúng ta lấy một đỉnh và lặp qua tất cả các cặp đỉnh để kiểm tra xem khoảng cách có nhỏ hơn khoảng cách hiện đã biết giữa và hay không. k W[i,j] i ⭢ k ⭢ j i j Giá trị nhỏ nhất được lưu trữ trong và bước #3 được lặp lại cho tiếp theo cho đến khi tất cả các đỉnh của được sử dụng làm . W[i,j] k G 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 ô của ma trận sẽ chứa khoảng cách của đường dẫn ngắn nhất giữa các đỉnh và hoặc giá trị nếu không có đường dẫn nào giữa chúng. W[i,j] W i j NO_EDGE 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 với khoảng cách có thể là đường dẫn mới từ đến qua đỉnh trung gian . W[i,j] i j 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 ⭢ 4 , 1 ⭢ , 2 ⭢ 4 :1 , và . 0 ⭢ 1 :2 1 ⭢ 3 :1 0 ⭢ 4 :10 2 ⭢ 4 :1 3 ⭢ 2 :1 3 ⭢ 4 :3 Tôi sử dụng định dạng “từ” ⭢ “đến” :”khoảng cách” từ để viết ra đường dẫn. bài đăng trước - Ghi chú của tác giả Chúng ta cũng biết rằng không có cạnh nào dẫn đến đỉnh , do đó việc thực thi thuật toán cho là vô nghĩa. Một điều hiển nhiên nữa là có một cạnh duy nhất ( ) dẫn từ đỉnh đến đỉnh , điều này cũng khiến cho việc thực thi tất cả ( là "from" ở đây) trở nên khá vô nghĩa và vì đỉnh có các cạnh có và , nên việc thực thi thuật toán cho bất kỳ nào không phải là hoặc ( là "to" ở đây) cũng không có ý nghĩa gì. 0 k = 0 0 ⭢ 1 0 1 i != 0 i 1 2 4 j 2 4 j Đó 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 , và . k = 1 i = 0 j = 2,4 Bước chân Con đường Bình luận 1 0 ⭢ 1 ⭢ 2 Đã tìm thấy đường đi. Khoảng cách = 3 (không có gì) 2 0 ⭢ 1 ⭢ 4 Đã tìm thấy đường đi. Khoảng cách = 8 (trước đây là 10). Chúng tôi đã tìm thấy hai đường dẫn: một đường dẫn mới ( ) và một lối tắt ( ). Cả hai đều đi qua đỉnh . Nếu chúng ta không lưu trữ thông tin này (thực tế là chúng ta đã đến và thông qua ) ở đâ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). 0 ⭢ 1 ⭢ 2 0 ⭢ 1 ⭢ 4 1 2 4 1 Vậy chúng ta nên làm gì? Chúng ta sẽ cập nhật ma trận với các giá trị mới (xem Hình 3a) và cũng lưu trữ giá trị của (là ) trong các ô và của ma trận mới có cùng kích thước với ma trận nhưng được khởi tạo bằng các giá trị (xem Hình 3b). W k k = 1 R[0,2] R[0,4] R W NO_EDGE Hiện tại, đừng tập trung vào ma trận 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 tiếp theo. R k = 2 Ở đâ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 nhưng lần này, chúng ta sẽ sử dụng ma trận thay vì đồ thị Hãy xem ma trận , đặc biệt là ở cột số 2 và hàng số 2 (Hình 4). k = 1, W G W Ở đây bạn có thể thấy, có hai đường dẫn đến đỉnh từ đỉnh và từ đỉnh (cột #2), và hai đường dẫn từ đỉnh đến đỉnh và đến đỉnh (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 , và . 2 0 1 2 3 4 k = 2 i = 0,1 j = 3,4 Bước chân Con đường Bình luận 1 0 ⭢ 2 ⭢ 3 Đã tìm thấy đường đi. Khoảng cách = 4 (không có gì) 2 0 ⭢ 2 ⭢ 4 Đường đi đã tìm thấy. Khoảng cách = 6 (là 8) 3 1 ⭢ 2 ⭢ 3 Đã tìm thấy đường đi. Khoảng cách = 2 (không có gì) 4 1 ⭢ 2 ⭢ 4 Đường đi đã tìm thấy. Khoảng cách = 4 (là 6) Như chúng tôi đã thực hiện trước đây, chúng tôi đang cập nhật các ô , , , với các khoảng cách mới và các ô , , và với (xem Hình 5). W[0,3] W[0,4] W[1,3] W[1,4] R[0,3] R[0,4] R[1,3] R[1,4] k = 2 Chỉ còn để xử lý (vì không có cạnh nào dẫn từ đỉnh đến bất kỳ đỉnh nào khác trong đồ thị). k = 3 4 Một lần nữa, chúng ta hãy xem xét ma trận (Hình 6). W Theo ma trận , có ba đường dẫn đến đỉnh từ các đỉnh , và (cột #3), và có một đường dẫn từ đỉnh đến đỉnh (hàng #3). Do đó, chúng ta có các đường dẫn sau để xử lý: W 3 0 1 2 3 4 Bước chân Con đường Bình luận 1 0 ⭢ 3 ⭢ 4 Đường đi đã tìm thấy. Khoảng cách = 5 (là 6) 2 1 ⭢ 3 ⭢ 4 Đường đi đã tìm thấy. Khoảng cách = 3 (là 4) 3 2 ⭢ 3 ⭢ 4 Đường đi đã tìm thấy. Khoảng cách = 2 (là 3) Đâ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 ô , , với khoảng cách mới và đặt các ô , , thành . W[0,4] W[1,4] W[2,4] R[0,4] R[1,4] R[2,4] 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ừ , ma trận hiện chứa tất cả các cặp đường đi ngắn nhất trong đồ thị Nhưng những gì được lưu trữ bên trong ma trận ? bài đăng trước W G 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 với giá trị hiện tại của . 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: (ở đây chúng ta đang đến trực tiếp từ ). R k i ⭢ k ⭢ j j 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 (chữ “đến”) đến đỉnh (chữ “từ”). j i 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ừ đến : i j Chuẩn bị mảng động rỗng X Bắt đầu bằng cách đọc giá trị từ ô . z R[i,j] Nếu là thì tuyến đường từ đến được tìm thấy và chúng ta nên tiến hành bước #7. z NO_EDGE i j Thêm vào trước mảng động z X Đọc giá trị của ô vào . R[i,z] z Lặp lại các bước #3, #4 và #5 cho đến khi đạt được điều kiện thoát ở #3. Thêm vào trước X. i Thêm vào j X Bây giờ mảng động chứa tuyến đường từ đến . X i j Xin lưu ý, thuật toán trên chỉ hoạt động với các đường dẫn hiện có. Nó cũng không hoàn hảo về mặt hiệu suất và chắc chắn có thể được tối ưu hóa. Tuy nhiên, trong phạm vi bài đăng này, nó được mô tả cụ thể theo cách giúp bạn dễ hiểu và tái tạo trên một tờ giấy hơn. - Ghi chú của tác giả 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ị của chúng ta và xây dựng lại một lộ trình từ đỉnh đến đỉnh (xem Hình 8). G 0 4 Sau đây là mô tả bằng văn bản về hình ảnh minh họa trên: Chúng ta bắt đầu bằng cách đọc giá trị từ , kết quả là . Theo thuật toán, điều này có nghĩa là tuyến đường đi đến đỉnh từ đỉnh (hiển thị bằng MÀU XANH LAM). R[0,4] 3 4 3 Vì giá trị của không phải là , chúng ta tiến hành và đọc giá trị của , kết quả là (hiển thị bằng màu XANH LÁ). R[0,4] NO_EDGE R[0,3] 2 Một lần nữa, vì giá trị của không phải là , chúng ta tiến hành và đọc giá trị của , kết quả là (hiển thị bằng MÀU ĐỎ). R[0,3] NO_EDGE R[0,2] 1 Cuối cùng, chúng ta đọc giá trị , dẫn đến giá trị , nghĩa là không còn đỉnh nào nữa ngoại trừ và góp phần vào tuyến đường. Do đó, tuyến đường kết quả là: 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 đến đỉnh . R[0,1] NO_EDGE 0 4 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 0 4 Một độc giả chu đáo có thể hỏi: Làm sao chúng ta có thể chắc chắn rằng mọi dữ liệu chúng ta đọc từ ma trận đều thuộc cùng một đường dẫn? R - Người đọc chu đáo Đâ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 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 Vì vậy, cuối cùng, mỗi hàng của ma trận 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. R W R 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ê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. bài đăng trước 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à: Mở rộng chữ ký hàm để bao gồm ma trận dưới dạng tham số riêng biệt – . R int[] routes Lưu k vào mỗi khi đường dẫn ngắn nhất được thay đổi (dòng: 2 và 14). routes 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: Mở rộng chữ ký hàm để bao gồm ma trận dưới dạng tham số riêng biệt – . R int[] routes Ở mỗi lần lặp lại, khởi tạo một vectơ mới gồm giá trị (dòng: 6). k Lưu giá trị vector vào mỗi khi đường dẫn ngắn nhất thay đổi (dòng: 31-32). k routes 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; } } } } } Một lời nhắc nhở nhỏ – Hoạt động trả về một vector mới trong đó các giá trị bằng giá trị nhỏ hơn trong hai giá trị tương ứng của vector đầu vào, tức là, nếu giá trị của vector bằng , thì hoạt động sẽ chọn một giá trị từ , nếu không, nó sẽ chọn một giá trị từ . Vector.ConditionalSelect lt_vec -1 ij_vec k_vec - Ghi chú của tác giả Đá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 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. BenchmarkDotNet 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 : 300, 600, 1200, 2400 và 4800 đỉnh. bài đăng trước Mã nguồn và biểu đồ thử nghiệm có sẵn trong kho lưu trữ trên GitHub. Biểu đồ thử nghiệm có thể được tìm thấy trong thư mục . tệp Data/Sparse-Graphs.zip Tất cả các điểm chuẩn trong bài đăng này đều được triển khai trong APSP02.cs . Dưới đây là kết quả chuẩn trong đó các phương thức và tương ứng với phiên bản gốc của thuật toán và các phương thức và 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). Baseline BaselineWithRoutes SpartialVectorOptimisations SpartialVectorOptimisationsWithRoutes Phương pháp Kích cỡ Trung bình (ms) Lỗi (ms) Độ lệch chuẩn (ms) Đường cơ sở 300 40.233 0,0572 0,0477 Đường cơ sởVới Tuyến đường 300 40.349 0,1284 0,1201 Tối ưu hóa vector một phần 300 4.472 0,0168 0,0140 Tối ưu hóa vector một phần với các tuyến đường 300 4.517 0,0218 0,0193 Đường cơ sở 600 324.637 5.6161 4.6897 Đường cơ sởVới Tuyến đường 600 321.173 1.4339 1.2711 Tối ưu hóa vector một phần 600 32.133 0,2151 0,1679 Tối ưu hóa vector một phần với các tuyến đường 600 34.646 0,1286 0,1073 Đường cơ sở 1200 2,656.024 6.9640 5.8153 Đường cơ sởVới Tuyến đường 1200 2,657.883 8.8814 7.4164 Tối ưu hóa vector một phần 1200 361.435 2.5877 2.2940 Tối ưu hóa vector một phần với các tuyến đường 1200 381.625 3.6975 3.2777 Đường cơ sở 2400 21.059.519 38.2291 33.8891 Đường cơ sởVới Tuyến đường 2400 20,954.852 56.4719 50.0609 Tối ưu hóa vector một phần 2400 3,029.488 12.1528 11.3677 Tối ưu hóa vector một phần với các tuyến đường 2400 3.079.006 8.6125 7.1918 Đường cơ sở 4800 164,869.803 547.6675 427.5828 Đường cơ sởVới Tuyến đường 4800 184,305.980 210.9535 164.6986 Tối ưu hóa vector một phần 4800 21.882,379 200.2820 177.5448 Tối ưu hóa vector một phần với các tuyến đường 4800 21.004.612 79.8752 70.8073 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 này với và để 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à 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 đó. chương trình Denis Bakhvalov Andrey Akinshin đậm 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 và thay vì một). W R 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 để biểu diễn mảng động): LinkedList<T> 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 và điền vào theo thứ tự ngược lại: sz 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ừ đến , 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 và không có cách nào để thoát khỏi nó. i j R 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! Bạn có thể tìm thấy bản triển khai của tất cả các thuật toán định tuyến trên GitHub trong tệp Routes.cs . 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ừ . 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". bài đăng trước 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!
