Công cụ phân tích lý thuyết đồ thị trực tuyến

Phân tích đường đi ngắn nhất với thuật toán Dijkstra

Công cụ này giải quyết bài toán tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị vô hướng có trọng số không âm. Nó sử dụng thuật toán Dijkstra, do đó không hỗ trợ trọng số âm, nhưng cho phép trọng số bằng 0. Đồ thị có thể có tối đa 500 đỉnh phân biệt và 1000 cạnh. Các cạnh song song được phép, và đồ thị được xem là vô hướng.

Ví dụ cụ thể

Giả sử bạn nhập ba cạnh: A,B,2, B,C,3, A,C,10. Chọn đỉnh bắt đầu là A và đỉnh kết thúc là C. Công cụ sẽ trả về khoảng cách ngắn nhất là 5 và đường đi A → B → C, vì tổng trọng số 2+3=5 nhỏ hơn cạnh trực tiếp A-C có trọng số 10.

Tham số và xử lý

Đầu vào là danh sách cạnh, mỗi cạnh gồm tên đỉnh (được cắt khoảng trắng) và trọng số không âm. Đỉnh bắt đầu và kết thúc phải xuất hiện trong danh sách cạnh. Nếu không có đường đi giữa hai đỉnh, công cụ hiển thị thông báo rõ ràng về việc đồ thị không kết nối.

Hạn chế

Công cụ không hỗ trợ đồ thị có hướng, không tính toán các thành phần liên thông, không hiển thị tọa độ, không tính các chỉ số trung tâm, không tìm cây khung nhỏ nhất, và không xử lý trọng số âm. Nó chỉ tìm một đường đi ngắn nhất; nếu có nhiều đường đi cùng khoảng cách, chỉ một đường được hiển thị.

Câu hỏi thường gặp

1. Tôi có thể nhập trọng số âm không?

Không. Thuật toán Dijkstra yêu cầu trọng số không âm. Nếu bạn nhập trọng số âm, công cụ sẽ từ chối xử lý. Trọng số bằng 0 được chấp nhận.

2. Điều gì xảy ra nếu tôi nhập nhiều hơn 1000 cạnh hoặc hơn 500 đỉnh?

Công cụ giới hạn tối đa 1000 cạnh và 500 đỉnh phân biệt. Nếu vượt quá, có thể xảy ra lỗi hoặc kết quả không chính xác. Hãy đảm bảo đầu vào nằm trong giới hạn.

3. Tôi có thể sử dụng tên đỉnh có khoảng trắng không?

Có, tên đỉnh được cắt khoảng trắng ở đầu và cuối, nhưng khoảng trắng bên trong vẫn được giữ nguyên. Ví dụ, “đỉnh A” và “đỉnh A ” được coi là cùng một đỉnh sau khi cắt.

Kiểm tra nhanh

• Nhập danh sách cạnh hợp lệ, mỗi cạnh trên một dòng.
• Chọn đỉnh bắt đầu và kết thúc có trong danh sách.
• Kiểm tra trọng số không âm.
• Xem kết quả đường đi và khoảng cách.