Đang chuẩn bị liên kết để tải về tài liệu:
Thuật Toán Và Thuật Giải part 8

Nút Arad đã có trong CLOSE. Tuy nhiên, do g(Arad) mới được tạo ra (có giá trị 280) lớn hơn g(Arad) lưu trong CLOSE (có giá trị 0) nên ta sẽ không cập nhật lại giá trị g và f’ của Arad lưu trong CLOSE. 3 nút còn lại : Fagaras, Oradea, Rimnicu đều không có trong cả OPEN và CLOSE nên ta sẽ đưa 3 nút này vào OPEN | Nút Arad đã có trong CLOSE. Tuy nhiên do g Arad mới được tạo ra có giá trị 280 lớn hơn g Arad lưu trong CLOSE có giá trị 0 nên ta sẽ không cập nhật lại giá trị g và E của Arad lưu trong CLOSE. 3 nút còn lại Fagaras Oradea Rimnicu đều không có trong cả OPEN và CLOSE nên ta sẽ đưa 3 nút này vào OPEN đặt cha của chúng là Sibiu. Như vậy đến bước này OPEN đã chứa tổng cộng 5 thành phố. OPEN Timisoara g 118 h 329 f 447 Cha Arad Zerind g 75 h 374 f 449 Cha Arad Fagaras g 239 h 178 f 417 Cha Sibiu Oradea g 291 h 380 f 617 Cha Sibiu R.Vilcea g 220 h 193 f 413 Cha Sibiu CLOSE Arad g 0 h 0 f 0 Sibiu g 140 h 253 f 393 Cha Arad Trong tập OPEN nút R.Vilcea là nút có giá trị E nhỏ nhất. Ta chọn Tmax R.Vilcea. Chuyển R.Vilcea từ OPEN sang CLOSE. Từ R.Vilcea có thể đi đến được 3 thành phố là Craiova Pitesti và Sibiu. Ta lần lượt tính giá trị E g và h của 3 thành phố này. h Sibiu 253 g Sibiu g R.Vilcea cost R.Vilcea Sibiu 220 80 300 E Sibiu g Sibiu h Sibiu 300 253 553 h Craiova 160 g Craiova g R.Vilcea cost R.Vilcea Craiova 220 146 366 f Craiova g Fagaras h Fagaras 366 160 526 h Pitesti 98 g Pitesti g R.Vilcea cost R.Vilcea Pitesti 220 97 317 f Pitesti g Oradea h Oradea 317 98 415 Sibiu đã có trong tập CLOSE. Tuy nhiên do g Sibiu mới có giá trị là 553 lớn hơn g Sibiu có giá trị là 393 nên ta sẽ không cập nhật lại các giá trị của Sibiu được lưu trong CLOSE. Còn lại 2 thành phố là Pitesti và Craiova đều không có trong cả OPEN và CLOSE nên ta sẽ đưa nó vào OPEN và đặt cha của chúng là R.Vilcea. OPEN Timisoara g 118 h 329 F 447 Cha Arad Zerind g 75 h 374 f 449 Cha Arad Fagaras g 239 h 178 f 417 Cha Sibiu Oradea g 291 h 380 f 617 Cha Sibiu Craiova g 366 h 160 f 526 Cha R.Vilcea Pitesti g 317 h 98 f 415 Cha R.Vilcea CLOSE Arad g 0 h 0 f 0 Sibiu g 140 h 253 f 393 Cha Arad R.Vilcea g 220 h 193 f 413 Cha Sibiu Đến đây trong tập OPEN nút tốt nhất là Pitesti từ Pitesti ta có thể đi đến được R.Vilcea Bucharest và Craiova. Lấy Pitesti ra khỏi OPEN và đặt nó vào CLOSE. Thực hiện tiếp theo tương .