Bài tự luận Một số bài toán thuộc chuyên đề Toán học 10–11–12 · Bài 5

Gán nhãn cho $P$ bằng $0\left( n_{P}=0 \right)$, các đỉnh khác bằng $\infty$. Khoanh tròn đỉnh $P$.
Tại các đỉnh kề với $P$, gồm $A,B$ và $C$, lần lượt ghi các nhãn 3, 1 và 5 (lần lượt bằng $n_P+w_{PA}$, $n_P+w_{PB}$, $n_P+w_{PC}$). Trong các đỉnh khác $P$, đỉnh có nhãn bé nhất là $B$. Khoanh tròn đỉnh $B$ (đỉnh gần đỉnh $P$ nhất, chỉ tính các đỉnh khác đỉnh $P$).
Trong các đỉnh chưa khoanh tròn, đỉnh kề với $B$ gồm $A,L$ và $C$. Tại $A$ giữ nguyên nhãn 3, do $n_{B}+w_{BA}=1+4=5>3$. Tại $L$, ghi nhãn 16 (bằng $n_{B}+w_{BL}$). Tại $C$, đổi nhãn 5 thành 4 (bằng $n_{B}+w_{BC}$). Lúc này, trong các đỉnh chưa khoanh tròn, đỉnh $A$ có nhãn nhỏ nhất. Khoanh tròn đỉnh $A$ (đỉnh khác $P$ gần đỉnh $P$ thứ hai).
Trong các đỉnh chưa khoanh tròn, đỉnh kề với $A$ chỉ có $L$. Tại $L$, giữ nguyên nhãn 16, do $n_{A}+w_{AL}=3+13=16$. Trong các đỉnh chưa khoanh tròn, đỉnh $C$ có nhãn nhỏ nhất. Khoanh tròn đỉnh $C$ (đỉnh gần đỉnh $P$ thứ ba).
Trong các đỉnh chưa khoanh tròn, đỉnh kề với $C$ gồm $M$ và $N$. Tại $M$, ghi nhãn 8 (bằng $n_{C}+w_{CM}$). Tại $N$, ghi nhãn 11 (bằng $n_{C}+w_{CN}$). Trong các đỉnh chưa khoanh tròn, đỉnh $M$ có nhãn nhỏ nhất. Khoanh tròn đỉnh $M$ (đỉnh gần đỉnh $P$ thứ tư).
Trong các đỉnh chưa khoanh tròn, đỉnh kề với $M$ gồm $L,N$ và $Q$. Tại $L$, giữ nguyên nhãn 16, do $n_{M}+w_{ML}=8+9=17>16$. Tại $N$, đổi nhãn 11 thành 10 (bằng $n_{M}+w_{MN}$). Tại $Q$, ghi nhãn 15 (bằng $n_{M}+w_{MQ}$). Trong các đỉnh chưa khoanh tròn, đỉnh $N$ có nhãn nhỏ nhất. Khoanh tròn đỉnh $N$ (đỉnh gần đỉnh $P$ thứ năm).
Trong các đỉnh chưa khoanh tròn, đỉnh kề với $N$ chỉ có $Q$. Tại $Q$, đổi nhãn 15 thành 14 (bằng $n_{N}+w_{NQ}$). Chỉ còn hai đỉnh $L$ và $Q$ chưa khoanh tròn, đỉnh $Q$ có nhãn nhỏ hơn. Khoanh tròn đỉnh $Q$ (đỉnh gần đỉnh $P$ thứ sáu).
Nhìn ngược lại các bước ở trên, ta thấy $n_{Q}=14=w_{PB}+w_{BC}+w_{CM}+w_{MN}+w_{NQ}=l_{PBCMNQ}.$
Suy ra $PBCMNQ$ là đường đi ngắn nhất từ $P$ đến $Q$, với độ dài bằng 14 (xem Hình 13).