Chứng minh. Trước tìm đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại của đồ sử rằng ở một bước lặp nào đó các nhãn cố định cho ta độ dài các đường đi ngắn nhất từ s đến các đinh có nhãn cố định,ta sẽ chứng minh rằng ở lần lặp tiếp theo nếu đỉnh u* thu được nhãn cố định thì d(u*) chính là dọ dài đường đi ngắn nhất từ s đén u*. Kí hiệu S1 là tập các đỉnh có nhãn cố định, S2 là tập các đỉnh có nhãn tạm thời. | Chứng minh. Trước tìm đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại của đồ sử rằng ở một bước lặp nào đó các nhãn cố định cho ta độ dài các đường đi ngắn nhất từ s đến các đinh có nhãn cố định ta sẽ chứng minh rằng ở lần lặp tiếp theo nếu đỉnh u thu được nhãn cố định thì d u chính là dọ dài đường đi ngắn nhất từ s đén u . Kí hiệu S1 là tập các đỉnh có nhãn cố định S2 là tập các đỉnh có nhãn tạm thời ở bước lặp đang thúc mỗi bước lặp nhãn tạm thời d v cho ta đoọdài của đường đi ngắn nhất từ s đến v chỉ qua những đỉnh nằm hoàn toàn trong tập sử rằn đường di ngắn nhất từ ú đến u không nằm tron trong tập S1 tức là nó đi qua ít nhất một đỉnh của tập z e S2 là đỉnh đầu tiên như vậy trên đường đi trọng số trên các cung là không âm nên đoạn đường từ s đến u cóđọ dài L 0 và d z d u - L d u . Bất đẳng thức này là mâu thuẫn với cách xác định đỉnh u là đỉnh có nhãn tạm thời nhỏ nhất. Vậy đường đin ngắn nhất từ s đến u phải nằm trọn trong tập S1 và vì thế d u là độ dài của ở lần lặp đầu tiên S1 s và sau mỗi lần lặp ta chỉ them vào S1 một đỉnh u nên giả thiết là d v cho độ dài đường đi ngắn nhất từ s đên v với mọi ve S1 là đúng với bước lặp đầu tiên .Theo qui nạp là suy ra thuật toán cho ta đường đi ngắn nhất từ s đến mọi đỉnh của đồ thị . Bây giờ sẽ đánh giá số phép toán cần thực hiện theo thuật toán. Ở mỗi bước lặp để tìm ra điểm u cần thực hiện O n phép toán để gán nhãn lại cũng cần thực hiện SVTH Nguyễn Công Hiếu_SBD 0041 - Trang 25 một số lượng phép toán cũng là O n .Thuật toán cần phải thực hiện n-1 bước lặp vậy thời gian tính toán của thuật toán là cỡ O n2 . Định lý được chứng minh. Khi đã tìm được độ dài đường đi ngắn nhất d v thì đưòng đi này có thể tìm dựa vào nhãn Trước v veV. Thí dụ 1 Tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại của đồ thị ở hình sau 7 4 1 2 4 3 5 SVTH Nguyễn Công Hiếu_SBD 0041 - Trang 26 Kết quả tính toán theo thuật toán được trình bày trong bản dưới ước viết thành 2 phần của nhãn theo
