Tìm hiểu các giải thuật tìm đường đi ngắn nhất bằng lý thuyết và thực tế, rồi mô phỏng trên môi trường đồ họa của windows

Giải thuật Floyd cho ta ma trận D là ma trận khoảng cách ngắn nhất của đồ thị. Và ma trận P cho ta xác định đường đi ngắn nhất này: Đường ngắn nhất từ đỉnh nguồn đến đỉnh đích được xác định bởi một dãy.

Thời gian thực hiện giải thuật Floyd tỉ lệ với n3. Ta có thể sử dụng giải thuật Dijkstra để giải quyết bài toán này. Trong trường hợp này ta phải áp dụng giải thuật Dijkstra n lần, mỗi lần chọn một đỉnh khác làm đỉnh nguồn, thời gian thực hiện của mỗi lần tỉ lệ với n2. Nếu ta sử dụng giải thuật Dijkstra với một nma trận chiều dài thì thời gian tổng cộng tỉ lệ với n* n2 = n3. Như vậy thời gian thực hiện của cả hai giải thuật Floyd và Dijkstra cùng tỉ lệ với n3, nhưng vì tính đơn giản của giải thuật Floyd mà giải thuật này có khả năng thực hiện nhanh hơn trong thực tế. Mặt khác, nếu chúng ta sử dụng giải thuật Dijkstra với một heap cùng với danh sách kề (có chứa chiều dài của các cung) thì thời gian thực hiện của mỗi lần tỉ lệ với (E + n)* log(n), do đó thời gian thực hiện tổng cộng của giải thuật Dijkstra tỉ lệ với n * ((E +n) * log(n)) = (E * n + n2) &* log(n). Nếu đồ thị đầy(E<< n2) ta nên sử dụng giải thuật Dijkstra, nếu đồ thị không đầy (E xấp xỉ với n2) thì ta nên sử dụng giải thuật Floyd.

Tuy nhiên với giải thuật Floyd ta thấy việc tìm đường đi ngắn nhất nó thực hiện một cách nhanh. Và nó cho ta con đường ngắn nhất giữa mọi cặp đỉnh trong đồ thị.

Giải thuat Floyd có thể áp dụng cho đồ thị vô hướng cũng như đồ thị có hướng: ta chỉ cần thay đổi cạnh vô hướng bằng một cạnh vô hướng. Tuy nhiên trong trường hợp này các phần tử trên đường chéo của ma trận cần đặt bằng không.