NenTang.vn
Ngôn ngữ lập trìnhLập trình C++ nâng cao - Cấu trúc dữ liệu và Giải thuật
Lab 5 - Tìm đường đi ngắn nhất từ đỉnh S đến tất cả các đỉnh còn lại trên đồ thị (sử dụng thuật toán Dijkstra)
Lý thuyết đồ thị
Thời lượng: 174 phútĐọc khoảng: 3 phút
Danh mục hình và bảng
Từ viết tắt
Nội dung bài học không khai báo từ viết tắt bằng thẻ abbr.
Nội dung bài học
Đề bài
Cho đồ thị có hướng có trọng số không âm G=<V,E> được biểu diễn dưới dạng danh sách cạnh trọng số. Hãy viết chương trình tìm đường đi ngắn nhất từ đỉnh S đến tất cả các đỉnh còn lại trên đồ thị. Dữ liệu đảm bảo có đường đi từ đỉnh S tới mọi đỉnh khác trên đồ thị.Input
- Dòng đầu tiên chứa 3 số n, m, s là số đỉnh, số cạnh của đồ thị và đỉnh bắt đầu (1 <= n <= 1000, 1 <= m <= n*(n-1)/2).
- M dòng tiếp theo, mỗi dòng là 2 số u, v biểu diễn cạnh u, v của đồ thị (1 <= u, v <= n).
- Ràng buộc: 1 <= n <= 1000; 1 <= m <= n*(n-1)/2; Trọng số các cạnh là số nguyên không âm không vượt quá 100;
Output
- Ghi ra file văn bản lab_t_output.OUT gồm đường đi ngắn nhất từ đỉnh S đến các đỉnh còn lại.
Sample 1
| Input | Output |
|
typescript |
typescript |
Sample 2
| Input | Output |
|
typescript |
typescript |
- Tool xem đồ thị online: https://csacademy.com/app/graph_editor/
Giải
- Source code:
cpp

