Cho bảng tính toán của router u sử dụng thuật toán Dijkstra như sau:

Giả sử router w bị hỏng. Tập N’ ở bước 2 trong mô hình sẽ gồm:

Trong thuật toán định tuyến Link State, mỗi router xây dựng một bản đồ (topology) hoàn chỉnh của mạng và tính toán bảng định tuyến của riêng mình dựa trên bản đồ đó. Do đó, số lượng bảng định tuyến trong mạng sẽ bằng với số lượng router. Câu hỏi cho biết có 5 routers, vậy sẽ có 5 bảng định tuyến. Thuật toán Link State không liên quan đến số lượng network để xác định số lượng bảng định tuyến của router.

Thuật toán Dijkstra là thuật toán tìm đường đi ngắn nhất từ một đỉnh nguồn tới tất cả các đỉnh còn lại trong một đồ thị có trọng số không âm. Bước 0 là bước khởi tạo, nơi chúng ta gán khoảng cách ban đầu cho tất cả các đỉnh. Đỉnh nguồn (ở đây là 'u') sẽ có khoảng cách là 0. Tất cả các đỉnh khác sẽ có khoảng cách ban đầu là vô cùng (∞) vì chúng ta chưa tìm được đường đi nào tới chúng. Riêng với đỉnh 'v', có một cạnh nối trực tiếp từ 'u' với trọng số là 2, nên khoảng cách ban đầu từ 'u' đến 'v' được cập nhật là 2. Tương tự, đỉnh 'w' có cạnh nối trực tiếp từ 'u' với trọng số là 4, nên khoảng cách ban đầu từ 'u' đến 'w' là 4. Đỉnh 'x' có cạnh nối trực tiếp từ 'u' với trọng số là 5, nên khoảng cách ban đầu từ 'u' đến 'x' là 5. Các đỉnh 'y' và 'z' không có cạnh nối trực tiếp với 'u', do đó khoảng cách ban đầu của chúng là vô cùng (∞). Vậy, sau bước 0, giá trị D(v), D(w), D(x), D(y), D(z) lần lượt là 2, 4, 5, ∞, ∞.

Câu hỏi kiểm tra kiến thức về thuật toán Dijkstra để tìm đường đi ngắn nhất trên đồ thị. Thuật toán Dijkstra hoạt động dựa trên nguyên tắc duyệt qua các đỉnh theo thứ tự khoảng cách tăng dần từ đỉnh nguồn, cập nhật khoảng cách đến các đỉnh lân cận nếu tìm được đường đi ngắn hơn.

Các bước thực hiện thuật toán Dijkstra với đỉnh xuất phát là 'u':
1. Khởi tạo: Khoảng cách từ 'u' đến chính nó là 0. Khoảng cách từ 'u' đến tất cả các đỉnh khác là vô cùng. Tập hợp các đỉnh đã xét (S) rỗng. Tập hợp các đỉnh chưa xét (V-S) bao gồm tất cả các đỉnh.
2. Lần lặp 1:
- Chọn đỉnh có khoảng cách nhỏ nhất chưa được xét: 'u' (khoảng cách 0).
- Đưa 'u' vào tập S. V-S còn lại: {v, w, x, y}.
- Cập nhật khoảng cách các đỉnh lân cận 'u':
- d(v) = min(inf, d(u) + cost(u,v)) = 0 + 2 = 2.
- d(w) = min(inf, d(u) + cost(u,w)) = 0 + 5 = 5.
- Các đỉnh x, y không có cạnh nối trực tiếp từ u.
- Khoảng cách hiện tại: u:0, v:2, w:5, x:inf, y:inf.
3. Lần lặp 2:
- Chọn đỉnh có khoảng cách nhỏ nhất chưa được xét: 'v' (khoảng cách 2).
- Đưa 'v' vào tập S. V-S còn lại: {w, x, y}.
- Cập nhật khoảng cách các đỉnh lân cận 'v':
- d(w) = min(5, d(v) + cost(v,w)) = min(5, 2 + 2) = 4.
- d(x) = min(inf, d(v) + cost(v,x)) = 2 + 3 = 5.
- Khoảng cách hiện tại: u:0, v:2, w:4, x:5, y:inf.
4. Lần lặp 3:
- Chọn đỉnh có khoảng cách nhỏ nhất chưa được xét: 'w' (khoảng cách 4).
- Đưa 'w' vào tập S. V-S còn lại: {x, y}.
- Cập nhật khoảng cách các đỉnh lân cận 'w':
- d(x) = min(5, d(w) + cost(w,x)) = min(5, 4 + 1) = 5 (không thay đổi).
- d(y) = min(inf, d(w) + cost(w,y)) = 4 + 7 = 11.
- Khoảng cách hiện tại: u:0, v:2, w:4, x:5, y:11.
5. Lần lặp 4:
- Chọn đỉnh có khoảng cách nhỏ nhất chưa được xét: 'x' (khoảng cách 5).
- Đưa 'x' vào tập S. V-S còn lại: {y}.
- Cập nhật khoảng cách các đỉnh lân cận 'x':
- d(y) = min(11, d(x) + cost(x,y)) = min(11, 5 + 3) = 8.
- Khoảng cách hiện tại: u:0, v:2, w:4, x:5, y:8.
6. Lần lặp 5:
- Chọn đỉnh có khoảng cách nhỏ nhất chưa được xét: 'y' (khoảng cách 8).
- Đưa 'y' vào tập S. V-S còn lại: {}.
- Không còn đỉnh nào để cập nhật.

Kết quả đường đi ngắn nhất từ 'u' đến các đỉnh còn lại:
- u đến u: 0
- u đến v: 2 (qua u)
- u đến w: 4 (qua v)
- u đến x: 5 (qua w)
- u đến y: 8 (qua x)

Xem xét các phương án:
- Phương án 1: Thể hiện cây đường đi ngắn nhất với các đỉnh và trọng số tương ứng là u(0), v(2), w(4), x(5), y(8). Đây là kết quả chính xác.
- Phương án 2: Khoảng cách đến w là 5, không phải 4, và khoảng cách đến y là 11, không phải 8. Sai.
- Phương án 3: Khoảng cách đến v là 2 (đúng), đến w là 5 (sai, phải là 4), đến x là 5 (đúng), đến y là 8 (đúng). Sai.
- Phương án 4: Đáp án khác. Sai vì đã có đáp án đúng.

Câu hỏi yêu cầu áp dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ đỉnh 'u' đến các đỉnh còn lại trong một đồ thị có trọng số. Sau khi xác định được các đường đi ngắn nhất, chúng ta cần xây dựng bảng forwarding (bảng định tuyến) cho đỉnh 'u'. Bảng forwarding này sẽ cho biết next hop (nút kế tiếp) để đến mỗi đỉnh đích theo đường đi ngắn nhất đã tìm được.

Các bước thực hiện thuật toán Dijkstra từ đỉnh u:
1. Khởi tạo khoảng cách từ u đến chính nó là 0, và đến tất cả các đỉnh khác là vô cùng. Đặt tập các đỉnh đã xét là rỗng.
2. Chọn đỉnh chưa xét có khoảng cách nhỏ nhất. Ban đầu là đỉnh u.
3. Cập nhật khoảng cách đến các đỉnh kề với đỉnh vừa chọn:
- Nếu khoảng cách từ u đến đỉnh kề qua đỉnh hiện tại nhỏ hơn khoảng cách đã biết đến đỉnh kề đó, thì cập nhật lại khoảng cách và ghi nhận đỉnh hiện tại là đỉnh trước đó (predecessor).
4. Đưa đỉnh vừa chọn vào tập các đỉnh đã xét.
5. Lặp lại bước 2-4 cho đến khi tất cả các đỉnh đã được xét.

Áp dụng vào đồ thị:
- Bắt đầu từ u: dist(u) = 0.
- Xét u:
- Đến v: dist(v) = 2 (predecessor: u).
- Đến w: dist(w) = 5 (predecessor: u).
- Chọn v (vì dist(v) = 2 < dist(w) = 5).
- Xét v:
- Cập nhật đến w: dist(w) = min(5, dist(v) + 3) = min(5, 2 + 3) = 5. (predecessor vẫn là u hoặc có thể là v tùy cách cài đặt, nhưng đường đi ngắn nhất vẫn qua u hoặc v). Tuy nhiên, theo hình, cạnh v-w có chi phí 3, nên đường đi u -> v -> w có tổng chi phí 2+3=5. Đường đi trực tiếp u -> w có chi phí 5. Nên có thể chọn next hop là v hoặc w.
- Đến x: dist(x) = dist(v) + 4 = 2 + 4 = 6 (predecessor: v).
- Chọn w (vì dist(w) = 5).
- Xét w:
- Cập nhật đến x: dist(x) = min(6, dist(w) + 1) = min(6, 5 + 1) = 6. (predecessor có thể là v hoặc w).
- Chọn x (vì dist(x) = 6).

Kết quả bảng Forwarding cho u:
Để xây dựng bảng forwarding, ta xem xét next hop trên đường đi ngắn nhất từ u.
- Đến u: Next hop là - (hoặc chính nó).
- Đến v: Đường đi ngắn nhất là u -> v (chi phí 2). Next hop là v.
- Đến w: Có hai đường đi ngắn nhất đều có chi phí 5: u -> w và u -> v -> w. Theo quy ước thông thường, ta chọn next hop là đỉnh đầu tiên trên đường đi ngắn nhất (hoặc theo quy tắc tie-breaking, ví dụ chọn đỉnh có nhãn nhỏ hơn). Trong trường hợp này, cả hai lựa chọn đều hợp lý, tuy nhiên, nếu xét theo quá trình Dijkstra, khi xét đỉnh u, ta có đường đến w là 5. Khi xét đỉnh v, ta cũng cập nhật đường đến w qua v là 5. Ta cần xem xét kỹ bảng ở đáp án. Nếu ta chọn next hop dựa trên thứ tự ưu tiên đỉnh hoặc nhãn đỉnh, hoặc dựa trên thứ tự khám phá. Tuy nhiên, đáp án 2 cho thấy next hop đến w là w. Điều này có thể xảy ra nếu ta ưu tiên đường đi trực tiếp nếu chi phí bằng nhau hoặc cách cài đặt cụ thể.
- Đến x: Đường đi ngắn nhất là u -> w -> x (chi phí 5+1=6) hoặc u -> v -> x (chi phí 2+4=6). Nếu next hop đến w là w và next hop đến x là w, thì đường đi là u -> w -> x. Nếu next hop đến v là v và next hop đến x là v, thì đường đi là u -> v -> x. Đáp án 2 cho thấy next hop đến x là w. Điều này có nghĩa là đường đi ngắn nhất đến x là u -> w -> x.

Xem xét lại:
- u đến u: 0
- u đến v: 2 (next hop: v)
- u đến w: 5 (next hop: w hoặc v - nếu chọn w thì là u->w; nếu chọn v thì là u->v->w)
- u đến x: 6 (khi qua w là 5+1=6, khi qua v là 2+4=6)

Nếu bảng forwarding là:
| Đích | Khoảng cách | Next Hop |
|---|---|---|
| u | 0 | - |
| v | 2 | v |
| w | 5 | w |
| x | 6 | w |

Thì đây là đáp án 2. Lí do cho next hop đến w là w có thể là vì đường đi trực tiếp u->w có chi phí 5, và đường đi u->v->w cũng có chi phí 5. Trong trường hợp chi phí bằng nhau, có thể ưu tiên đường đi trực tiếp hoặc đỉnh có nhãn nhỏ hơn (nếu có quy tắc).

Đối với đỉnh x, khoảng cách ngắn nhất là 6. Có hai đường: u->v->x (next hop từ u là v) và u->w->x (next hop từ u là w). Nếu đáp án chọn next hop là w, thì nghĩa là đường đi u->w->x được chọn. Điều này phù hợp với đáp án 2.

Trong mạng máy tính, một miền đụng độ (collision domain) là một phần của mạng nơi các gói tin có thể xung đột với nhau. Mỗi cổng của một hub tạo ra một miền đụng độ duy nhất cho tất cả các thiết bị kết nối với nó. Ngược lại, mỗi cổng của một switch tạo ra một miền đụng độ riêng biệt. Trong sơ đồ:

- Hub (kết nối A, B, C, D): Tất cả 4 máy tính này chia sẻ chung một miền đụng độ. Do đó, ta có 1 miền đụng độ từ hub.
- Switch (kết nối E, F, G): Mỗi cổng của switch tạo ra một miền đụng độ riêng. Máy tính E nằm trong một miền đụng độ, máy tính F nằm trong một miền đụng độ khác, và máy tính G nằm trong một miền đụng độ thứ ba. Do đó, ta có 3 miền đụng độ từ switch.

Tổng số miền đụng độ là 1 (từ hub) + 3 (từ switch) = 4.

Tuy nhiên, các đáp án được đưa ra là 3, 11, 5. Vì 4 không có trong các lựa chọn, ta cần xem xét lại cách hiểu hoặc khả năng câu hỏi có sai sót. Trong các câu hỏi trắc nghiệm về chủ đề này, đáp án phổ biến và chính xác nhất dựa trên định nghĩa là 4.

Nếu buộc phải chọn một đáp án và giả định có một quy ước đếm khác hoặc lỗi trong câu hỏi:

- Đáp án 3: Có thể là người ra đề chỉ đếm số miền đụng độ do switch tạo ra (3 miền), bỏ qua miền đụng độ của hub. Đây là cách đếm không đầy đủ.
- Đáp án 5: Không có cách đếm chuẩn nào cho ra kết quả 5 trong trường hợp này. Một cách đếm sai lầm có thể là đếm 1 cho hub và 4 miền không xác định hoặc đếm các thiết bị một cách không chính xác.

Giả sử đáp án đúng là 3, thì cách giải thích có thể là chỉ đếm các miền đụng độ riêng biệt do switch tạo ra (3 miền cho E, F, G).