Bài toán tìm đường đi ngắn nhất

Trọng số của cạnh a được kí hiệu là gì?

• w_a

• l_a

• n_a

• f_a

Answer explanation

Câu này chắc bạn nào cũng đúng hết nhỉ????

Trọng số của cạnh AD và FC lần lượt là:

• 4; 11

• 20; 5

• 11; 5

• 20; 11

Answer explanation

Quan sát hình một lần nữa nào!

Nguyên lí của thuật toán Dijkstra: Cách tìm đường đi ngắn nhất từ A đến T là

• Tìm lần lượt các đỉnh (khác A) xa A nhất, xa thứ 2, thứ 3,... cho đến khi T là một trong các đỉnh đó.

• Tìm lần lượt các cạnh gần A nhất, gần A thứ 2, thứ 3,... cho đến khi T là một trong các cạnh đó

• Tìm lần lượt các đỉnh (khác A) gần A nhất, gần A thứ 2, thứ 3,... cho đến khi T là một trong các đỉnh đó

• Tìm lần lượt các đỉnh gần A nhất, gần A thứ 2, thứ 3,... cho đến khi T là một trong các đỉnh đó

Answer explanation

Các bạn nhớ KHÁC A nữa nha.
Gần A nhất nữaaaa
(Đoạn 3 trang 62)

Đường đi ngắn nhất từ đỉnh E đến đỉnh A là

• ECBA

• EDBCA

• ECA

• EBA

Có phải tất cả thuật toán tìm đường đi ngắn nhất của Dijkstra là 4 bước không?

• Đúng rồi bạn

• Không phải đâu

Nhà bạn Agon ở đỉnh A, nhà bạn Florine ở đỉnh F. Hỏi đường đi ngắn nhất từ nhà bạn Agon đến nhà bạn Florine là đường đi nào với quãng đường là bao nhiêu

• AMDF; 17

• AMNF; 17

• ABCF; 16

• AENF; 16

Answer explanation

Khoảng cách từ nhà Agon đến Florine là 17. Đó là quãng đường ngắn nhất là AMNF

Hình bên có tất cả 5 đỉnh. Hỏi, có tất cả bao nhiêu trọng số từ hình bên?

(a)  

Answer explanation

Thông tin trước chỉ đánh lừa bạn thôi. Trọng số và các đỉnh không liên quan gì đến nhau

Việc tìm đường đi ngắn nhất trên Google Maps có phải là ứng dụng của bài học này hay không?

• Đúng vậy

• Không phải

Answer explanation

(Câu cho điểm)

Một trong các đường đi ngắn nhất từ A đến E là?

• ABCE

• ABDE

• ADBE

• AFCE

Answer explanation

Ở đây, có 2 đường đi ngắn nhất từ A đến E là ABDE và ACDE với quãng đường là 9. Tuy nhiên đề bài yêu cầu một trong hai đường; có thể là ABDE hoặc ACDE. Tuy nhiên đáp án chỉ có ABDE nên ta khoanh câu đó.

Ngày mai là ngày đi học đầu tiên của em An, nhà An hiện tại đang ở đỉnh A, các trọng số là thời gian (phút) em An đi trong quãng đường đó. Trường Tiểu học H nằm ở đỉnh H. Hỏi em An phải đi những con đường nào để đến trường sớm nhất?

(a)  

Answer explanation

Em An phải đi qua quãng đường sau: ACEH. Với thời gian tổng là 17 phút