Công cụ phân tích lý thuyết đồ thị trực tuyến
Nhập tối đa 1000 cạnh, chọn đỉnh đầu và cuối, công cụ dùng Dijkstra để tính khoảng cách và đường đi ngắn nhất trong đồ thị vô hướng.
Bắt đầu sử dụng
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ông cụ từ chối đầu vào và hiển thị lỗi. 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.
Dùng dấu phẩy ASCII để ngăn trường và dấu chấm thập phân cho trọng số. A,B có trọng số 1; A,B, hiện được đọc là 0, vì vậy hãy ghi rõ trọng số. Bỏ qua dòng trống. Tên phân biệt hoa thường, chỉ bỏ khoảng trắng ngoài và không được chứa dấu phẩy. Nếu đầu và cuối trùng nhau, khoảng cách là 0 và đường đi chứa đỉnh đó. Tổng đỉnh tính cả danh sách. Phép cộng dấu phẩy động có thể làm tròn; khoảng cách có thể đi tới nhưng vượt phạm vi hữu hạn sẽ gây lỗi số.
Quá trình xử lý diễn ra cục bộ trong trình duyệt.