Đề bài

Trong một trò chơi, người chơi muốn tìm đường đi ngắn nhất để đi từ A đến P, biết từ A đến P có những đường đi như hình vẽ và khoảng cách giữa các vị trí được cho trên hình. Đường đi thỏa mãn điều kiện trên nhận giá trị nhỏ nhất là bao nhiêu?

Phương pháp giải

Thuật toán Dijkstra.

Lời giải của GV Loigiaihay.com

Đáp án :

Áp dụng thuật toán Dijkstra, ta tìm được đường đi ngắn nhất từ A đến P là:

A > M > P: 7 + 8 + 6 = 21.

Mở rộng

Thuật toán Dijkstra

Sử dụng khi cần tìm đường đi ngắn nhất mà không cần đi qua tất cả các đỉnh hay các cạnh.

Bước 1: Gán khoảng cách từ đỉnh nguồn đến chính nó là 0, và đến tất cả các đỉnh khác là vô cùng.

Bước 2: Gọi đỉnh chưa xét với giá trị đánh dấu nhỏ nhất là C.

Bước 3: Với mỗi đỉnh kề (N) với đỉnh hiện tại C và chưa được xét, tính toán khoảng cách mới từ nguồn qua C đến N (bằng khoảng cách của C cộng với trọng số cạnh nối C và N).... Nếu khoảng cách mới này nhỏ hơn khoảng cách hiện đang gán cho đỉnh N, hãy cập nhật lại khoảng cách của N bằng giá trị nhỏ hơn đó.

Bước 4: Đánh dấu đỉnh C là đã xét xong.

Bước 5: Tiếp tục lặp lại bước 2 cho đến khi tất cả các đỉnh đã được xét.

Báo lỗi - Góp ý

BÌNH LUẬN

Danh sách bình luận

Đang tải bình luận...

Các bài tập cùng chuyên đề

Bài 1 :

Một trò chởi điện tử quy định như sau: Có 4 trụ A, B, C, D với số lượng các thử thách trên đường đi giữa các cặp trụ được mô tả trong hình bên. Người chơi xuất phát từ một trụ nào đó, đi qua tất cả các trụ còn lại, mỗi khi đi qua một trụ thì trụ đó sẽ bị phá hủy và không thể quay trở lại trụ đó được nữa, nhưng người chơi vẫn phải trở về trụ ban đầu. Tổng số thử thách của đường đi thoả mãn điều kiện trên nhận giá trị nhỏ nhất là bao nhiêu?

Xem lời giải >>

Bài 2 :

Một công ty vận tải cần giao hàng đến tất cả các thành phố A, B, C, D, E (hình vẽ bên dưới). Chi phí di chuyển giữa các thành phố được mô tả trên hình. Xe giao hàng của công ty xuất phát từ một thành phố trong năm thành phố trên đi qua tất cả các thành phố còn lại đúng một lần sau đó trở lại thành phố ban đầu. Tìm chi phí thấp nhất của xe giao hàng.

Xem lời giải >>

Bài 3 :

Công ty giao hàng nhanh có 4 kho hàng A, B, C và D . Quản lý muốn lên kế hoạch cho xe giao hàng đi qua tất cả các kho hàng để lấy hàng và quay lại kho hàng ban đầu, với điều kiện là mỗi kho hàng chỉ ghé qua một lần. Khoảng cách giữa các kho hàng (km) được mô tả trong hình bên. Quãng đường ngắn nhất để xe
giao hàng hoàn thành việc lấy hàng ở các kho và quay trở lại kho hàng ban đầu là bao nhiêu?

Xem lời giải >>

Bài 4 :

Một nhân viên của bảo tàng nghệ thuật đang có kế hoạch giới thiệu nội dung cuộc triển lãm của bảo tàng đến ba trường học trong khu vực. Người đó muốn đến từng trường và quay trở lại bảo tàng sau khi thăm cả ba trường. Thời gian di chuyển (đơn vị: phút) giữa các trường học và giữa bảo tàng với mỗi trường học được mô tả trong hình vẽ.Tìm thời gian đi ít nhất để thực hiện chu trình trên.

Xem lời giải >>

Bài 5 :

Từ kho D xe bưu chính đến lấy thư từ các hộp thư tại E, F, G và H rồi quay lại kho. Sơ đồ bên dưới hiển thị thời gian xe bưu chính di chuyển giữa các hộp thư (đơn vị: phút). Thời gian ngắn nhất để xe bưu chính thực hiện điều đó là bao nhiêu phút?

Xem lời giải >>

Bài 6 :

Công ty A có kế hoạch tổ chức tour du lịch tâm linh tại tỉnh Bắc Giang đi qua 5 địa điểm: Đền Xương Giang, Chùa Bổ Đà, Chùa Vĩnh Nghiêm, Thiền viện Trúc lâm Phượng Hoàng, Đền Ngọc Lâm. Hành khách sẽ xuất phát từ Đền Xương Giang và đi thăm mỗi địa điểm đúng một lần. Qua khảo sát thực địa, công ty xây dựng được lược đồ như hình (khoảng cách giữa mỗi cặp địa điểm được ghi trên đường nói). Để tiết kiệm chi phí, công ty dự định chọn tuyến đường có tổng độ dài ngắn nhất. Độ dài của tuyến đường này là bao nhiêu km (làm tròn đến hàng phần mười)?

Xem lời giải >>

Bài 7 :

Một nhân viên của bảo tàng nghệ thuật đang có kế hoạch giới thiệu nội dung cuộc triển lãm của bảo tàng đến ba trường học trong khu vực. Người đó muốn đến từng trường và quay trở lại bảo tàng sau khi thăm cả ba trường. Thời gian di chuyển (đơn vị: phút) giữa các trường học và giữa bảo tàng với mỗi trường học được mô tả trong Hình 35.

Tìm chu trình xuất phát từ viện bảo tàng sao cho thời gian đi là ít nhất.

Xem lời giải >>

Bài 8 :

Một bác Shipper giao hàng xuất phát từ kho A để lấy hàng và đi giao tất cả các con đường sau đó lại trở về kho A để trả lại những hàng hóa mà khách hàng chưa nhận. Con đường có sơ đồ và thời gian giao hàng (phút) trên mỗi con đường được mô tả trong hình sau:

Thời gian ngắn nhất để bác Shipper hoàn thành công việc trên là bao nhiêu phút?

Xem lời giải >>

Bài 9 :

Có năm địa điểm A, B, C, D, E. Một số địa điểm có đường đi tới nhau mô tả bằng các cạnh với độ dài quãng đường tính theo kilomet cho bởi số gắn với cạnh đó như hình vẽ. Một người đưa thư xuất phát từ bưu điện C cần đi qua tất cả các đường (mỗi đường đi qua ít nhất một lần), và sau đó phải trở về vị trí ban đầu C. Tổng số kilomet mà người đưa thư cần phải đi nhỏ nhất bằng bao nhiêu?

Xem lời giải >>

Bài 10 :

Cho sơ đồ như trên Hình 2.28, ở đó A, B, C, D, E, F là các địa điểm nối với nhau bởi các con đường với độ dài của mỗi con đường được cho như trên hình.

a) Hãy chỉ ra 2 đường đi từ A đến F và so sánh độ dài của hai đường đi đó.

b) Với mỗi đỉnh V của sơ đồ trên Hình 2.28, ta gắn số I(V) là khoảng cách ngắn nhất để đi từ A đến V và gọi là nhãn vĩnh viễn của đỉnh V. Như vậy, ta có ngay I(A) = 0. Dựa vào Hình 2.28, hãy tìm các nhãn vĩnh viễn I(B), I(C) của hai đỉnh kề với A là B, C.

Xem lời giải >>

Bài 11 :

Tìm đường đi ngắn nhất từ A đến D trong đồ thị có trọng số trên Hình 2.33.

Xem lời giải >>

Bài 12 :

Tìm đường đi ngắn nhất từ đỉnh S đến mỗi đỉnh khác của đồ thị có trọng số trên Hình 2.34.

Xem lời giải >>

Bài 13 :

Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.35.

Xem lời giải >>

Bài 14 :

Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.36.

Xem lời giải >>

Bài 15 :

Viết tập hợp các đỉnh và tập hợp các cạnh của mỗi đồ thị sau:

Xem lời giải >>

Bài 16 :

Vẽ đồ thị G = (V, E) với các đỉnh và các cạnh như sau:

V = {1; 2; 3; 4; 5; 6; 7; 8} và E = {12; 13; 23; 34; 35; 67; 68; 78}.

Đồ thị này có phải là đơn đồ thị không? Có phải là đồ thị đầy đủ không?

Xem lời giải >>

Bài 17 :

Giải bài toán người đưa thư với đồ thị có trọng số trên Hình 2.41.

Xem lời giải >>

Bài 18 :

Giải bài toán người đưa thư với đồ thị có trọng số trên Hình 2.42.

Xem lời giải >>

Bài 19 :

Như chúng ta đã biết, Lí thuyết đồ thị ra đời trong quá trình khái quát, mô phỏng những vấn đề của khoa học và thực tiễn thành những mô hình toán học. Vì thế, các kết quả của Lí thuyết đồ thị có nhiều ứng dụng trong khoa học và thực tiễn.

Lí thuyết đồ thị có thể giải quyết những vấn đề thực tiễn nào?

Xem lời giải >>

Bài 20 :

Sử dụng thuật toán láng giềng gần nhất để giải bài toán trong Hoạt động 2.

Giả sử có sáu địa điểm A, B, C, D, E, F được nối với nhau theo những con đường với độ dài (đơn vị: kilômét) được mô tả bằng đồ thị có trọng số ở Hình 24. Người giao hàng cần đi giao hàng tại sáu địa điểm trên. Người giao hàng xuất phát từ một địa điểm nào đó, đi qua các địa điểm còn lại để giao hàng và trở về địa điểm ban đầu. Hãy tìm một đường đi thỏa mãn điều kiện trên cho người giao hàng sao cho quãng đường mà người giao hàng phải di chuyển là ngắn nhất.

Xem lời giải >>

Bài 21 :

Giả sử có sáu địa điểm A, B, C, D, E, F được nối với nhau theo những con đường với độ dài (đơn vị: kilômét) được mô tả bằng đồ thị có trọng số ở Hình 24. Người giao hàng cần đi giao hàng tại sáu địa điểm trên. Người giao hàng xuất phát từ một địa điểm nào đó, đi qua các địa điểm còn lại để giao hàng và trở về địa điểm ban đầu. Hãy tìm một đường đi thỏa mãn điều kiện trên cho người giao hàng sao cho quãng đường mà người giao hàng phải di chuyển là ngắn nhất.

Xem lời giải >>

Bài 22 :

Hãy cho ví dụ về đồ thị có trọng số.

Xem lời giải >>

Bài 23 :

Giả sử ba địa điểm A, B, C được nối với nhau theo những con đường AB, BC, CA với độ dài lần lượt là 15 km, 20 km, 16 km. Sử dụng đồ thị để mô tả tình huống đó.

Xem lời giải >>

Bài 24 :

Có bốn địa điểm với độ dài quãng đường giữa các địa điểm (đơn vị: kilômét) mô tả trong Hình 32. Sử dụng thuật toán láng giềng gần nhất, tìm các chu trình xuất phát từ một đỉnh đi qua tất cả các địa điểm, mỗi địa điểm đúng một lần sao cho tổng độ dài các cạnh của chu trình là nhỏ nhất.

Xem lời giải >>

Bài 25 :

Giả sử chi phí di chuyển giữa các địa điểm được mô tả ở Hình 33 (đơn vị: nghìn đồng). Ta nên chọn theo chu trình nào đi qua tất cả các địa điểm để tổng chi phí di chuyển là thấp nhất? Chi phí thấp nhất đó bằng bao nhiêu?

Xem lời giải >>

Bài 26 :

Sử dụng thuật toán láng giềng gần nhất, hãy giải bài toán người giao hàng đối với đồ thị ở Hình 34, số ghi trên mỗi cạnh của đồ thị mô tả độ dài quãng đường giữa các địa điểm (đơn vị: kilômét).

Xem lời giải >>

Bài 27 :

Phần mềm chỉ đường thường chỉ ra đường đi ngắn nhất khi người dùng muốn tìm đường đi từ một địa điểm đến một địa điểm khác.

Làm thế nào để tìm ra đường đi đó?

Xem lời giải >>

Bài 28 :

Cho đồ thị có trọng số như Hình 5.

a) Chỉ ra trọng số của các cạnh AE, MN, CN.

b) Tính độ dài của các đường đi ABEN, EMFNE.

c) Chỉ ra ba đường đi khác nhau từ A đến D và tính độ dài của chúng.

d) Đường đi EMF có phải là đường đi ngắn nhất từ E đến F không?

Xem lời giải >>

Bài 29 :

Để biểu diễn các con đường nối các giao lộ cùng với độ dài của chúng như sơ đồ ở Hình 1, một học sinh đã vẽ đồ thị như Hình 2. Chỉ ra các cạnh và số biểu diễn độ dài con đường còn thiếu trong Hình 2.

Xem lời giải >>

Bài 30 :

Trong đồ thị có trọng số ở Hình 15, mỗi cạnh biểu diễn một tuyến xe buýt giữa hai bến trong các bến xe A, B, C, D, E và F, trọng số của mỗi cạnh biểu diễn thời gian tính bằng giờ của tuyến xe buýt tương ứng. Một người cần ít nhất bao nhiêu thời gian để di chuyển từ bến A đến bến C bằng xe buýt của các tuyến trên? Biết rằng thời gian tại bến để chuyển tiếp từ tuyến này qua tuyến kia là không đáng kể.

Xem lời giải >>