Tôi tiếp tục cố gắng để google này, nhưng kết quả tôi tìm thấy chỉ là thêm vào sự nhầm lẫn của tôi. Có vẻ như nó có thể được sử dụng cho cả hai? Nếu vậy, nó được thiết kế cho theo mặc định và những gì cần phải thay đổi để làm cho nó hoạt động theo cách không mặc định (cho dù đó là đạo diễn hay không được hướng dẫn)?Thuật toán của Dijkstra cho đồ thị có hướng hoặc không được chiếu?
Edit: để tham khảo, tôi đã có một vấn đề học kỳ cuối cùng mà tôi đã được đưa ra một danh sách như thế này (sân bay):
AER,KZN,1.8835
ASF,KZN,1.3005
ASF,MRV,1.1204
CEK,KZN,1.9263
CEK,OVB,1.6733
DME,KZN,1.7892
DME,NBC,2.2319
DME,UUA,2.3786
EGO,KGD,1.4649
EGO,KZN,1.2603
GYD,NBC,2.0755
Tôi đã nói với nó được đạo diễn, và được yêu cầu tìm ra con đường ngắn nhất. Tôi đưa nó vào thuật toán của Dijkstra mà tôi tìm thấy trên Github (nó là một midterm máy tính mở nên chúng ta không có đủ thời gian để viết thuật toán từ đầu) và giáo sư của tôi nói con đường ngắn nhất mà nó trả về là không chính xác và thậm chí không phải là một con đường có thể bởi vì danh sách được cho là được hướng dẫn. Tôi đã không chắc chắn nếu tôi có nghĩa vụ phải sau đó sửa đổi các thuật toán hoặc danh sách để thực hiện điều chỉnh này. Nó đã kết thúc được trường hợp con đường ngắn nhất thứ 2 nó trở lại thực sự là con đường ngắn nhất, nhưng tôi vẫn tự hỏi vấn đề là gì.
Vì vậy, nếu danh sách của tôi không bao gồm mục trùng lặp nhưng được đảo ngược cho mỗi cạnh, nó sẽ cho tôi đường dẫn ngắn nhất được hướng dẫn? Bởi vì tôi đã được cho biết danh sách mà tôi đã được chỉ dẫn, nhưng việc thực hiện Dijkstra của tôi đã sử dụng đã cho tôi một con đường ngắn nhất. – Austin
Vâng, điều này nghe có vẻ như việc thực hiện bạn tìm thấy diễn giải các mục trong danh sách của bạn như là không được hướng dẫn, mà không phải là những gì bạn muốn, do đó bạn có lẽ nên chỉ thực hiện các thuật toán chính mình. Những cái tôi biết thường chỉ sử dụng một danh sách kề (đó là một danh sách chứa thông tin về các nút mà bạn có thể tiếp cận từ một nút cho trước * => các kết nối được hướng dẫn *). Đây là lý do tại sao tôi nói bạn không phải làm bất cứ điều gì để làm cho nó hoạt động cho đồ thị vô hướng, tuy nhiên, nếu thuật toán của bạn vì lý do gì tự động diễn giải các kết nối như hai chiều nó cần phải được thay đổi. – Keiwan
@Keiwan Bài đăng này https://stackoverflow.com/questions/22649416/why-cant-prims-or-kruskals-algorithms-be-used-on-a-directed-graph cho biết thuật toán prims sẽ thất bại đối với đồ thị được chỉ dẫn. Vì vậy, Dijkstras mà gần giống như mồi cũng sẽ thất bại cho các ví dụ được đưa ra trong bài viết. – WSS