JavaScript is required

Cho mô hình đồ thị biểu diễn sự kết nối và chi phí kết nối giữa các router như hình minh họa bên dưới. Sử dụng thuật toán Dijkstra để xác định đường đi ngắn nhất từ đỉnh u đến các đỉnh còn lại.

Node số 3 trong tập N’ (tập các node mà chi phí đường đi thấp nhất đã được xác định) là ?

A.

x

B.

y

C.

w

D.

v

Trả lời:

Đáp án đúng: D


Để xác định node nào được thêm vào tập N' (tập các node mà chi phí đường đi ngắn nhất đã được xác định) tiếp theo, chúng ta cần mô phỏng thuật toán Dijkstra. Thuật toán Dijkstra hoạt động bằng cách duy trì một tập các đỉnh đã được xử lý (N') và một tập các đỉnh chưa được xử lý. Ban đầu, N' chỉ chứa đỉnh nguồn (giả sử là 'u' dựa trên ngữ cảnh câu hỏi). Thuật toán lặp lại việc chọn đỉnh chưa được xử lý có khoảng cách nhỏ nhất đến đỉnh nguồn, thêm nó vào N', và sau đó cập nhật khoảng cách đến các đỉnh lân cận của nó. Giả sử đỉnh nguồn là 'u' và các nhãn khoảng cách ban đầu như sau: - dist(u) = 0 - dist(v) = ∞ - dist(w) = ∞ - dist(x) = ∞ - dist(y) = ∞ **Bước 1:** Đỉnh 'u' được chọn vì có khoảng cách nhỏ nhất (0). Tập N' = {u}. Cập nhật khoảng cách đến các đỉnh lân cận của 'u': - dist(v) = 2 (qua cạnh (u,v)) - dist(x) = 5 (qua cạnh (u,x)) **Bước 2:** Chọn đỉnh chưa được xử lý có khoảng cách nhỏ nhất. Trong các đỉnh còn lại {v, w, x, y}, đỉnh có khoảng cách nhỏ nhất là 'v' với dist(v) = 2. Vậy, node số 3 trong tập N' (tập các node mà chi phí đường đi thấp nhất đã được xác định) ở bước này là 'v'.

This document is a final exam paper for the 'Introduction to Computer Networks' course from HK2 2018-2019. It contains multiple-choice questions covering fundamental networking concepts such as network devices, IP addressing, subnetting, routing protocols, TCP/IP functionalities, ARP, DHCP, HTTP, NAT, MAC addresses, IMAP, and port numbers.


40 câu hỏi 75 phút

Câu hỏi liên quan