Tìm đường đi ngắn nhất

The Shortest Path

Đường đi ngắn nhất

Đường 1 chiều và đường 2 chiều là gì?

• Chiều mũi tên từ A đến B chỉ con đường một chiều từ A đến B.

• Nếu đoạn nối từ A đến B không có mũi tên thì có con đường hai chiều từ A đến B.

Độ dài đường đi là gì?

• Con số ghi trên đoạn nối từ điểm A đến điểm B là độ dài đường đi từ A đến B.

• Nếu gán điểm A là số 0, thì điểm B sẽ được gán là độ dài của đường đi từ A đến B.

Đường đi ngắn nhất là gì?

• Đường đi ngắn nhất từ A đến F là con đường có tổng độ dài nhỏ nhất trong số tất cả các con đường có thể đi từ A đến F.

Multiple Choice

Độ dài đường đi ngắn nhất từ điểm S đến điểm E là:

• 8

• 9

• 10

• 12

Bảng số Pascal & Số đường đi ngắn nhất

(1) Hàng đầu tiền chứa 1 số hạng, hàng thứ 2 chứa hai số hạng, và cứ tiếp tục như thế.

(2) Số ở hai bên "mép" đều là 1.

(3) Mỗi số là tổng của hai số trước ở trên nó.

Đếm số đường đi ngắn nhất bằng cách thông thường

Đếm số đường đi ngắn nhất bằng phương pháp Pascal

Fill in the Blank

Có bao nhiêu con đường đi từ điểm A đến điểm B theo hướng 

 $\uparrow$  và  $\longrightarrow$ ?

Multiple Choice

Có bao nhiêu con đường đi từ điểm A đến điểm B theo hướng

 $\uparrow$  và  $\longrightarrow$ ?

• 2

• 4

• 6

• 8

• 10

Multiple Choice

Có bao nhiêu con đường ngắn nhất có thể đi từ điểm A đến điểm B?

• 7

• 8

• 9

• 10

Multiple Choice

Có bao nhiêu con đường ngắn nhất có thể đi từ điểm A đến điểm B?

• 18

• 20

• 22

• 24

THANK YOU!

Tư duy tìm đường đi ngắn nhất từ điểm A đến điểm B như thế nào?

• Bước 1: Gán đỉnh B là số 0 và chúng ta gọi nó là đỉnh hiện tại.

• Bước 2: Gán các đỉnh kề và nối đến đỉnh hiện tại là giá trị khoảng cách từ nó đến đỉnh hiện tại.

• Bước 3: Đánh dấu đỉnh số 0 đã thăm và chúng ta không nhìn vào đỉnh này nữa.

• Bước 4: Đánh dấu đỉnh có khoảng cách nhỏ nhất là đỉnh hiện tại và lặp lại bước 2.