Здравствуйте, Иван Васильевич Митяев!

Положим B[sub]8[/sub][sup]*[/sup] = 0, B[sub]1[/sub] = B[sub]2[/sub] = B[sub]3[/sub] = B[sub]4[/sub] = B[sub]5[/sub] = B[sub]6[/sub] = B[sub]7[/sub] = B[sub]9[/sub] = B[sub]10[/sub] = [$8734$]. Метка вершины 8 постоянна.

1. Смежными с вершиной 8 являются вершины 5, 7 и 10. Пересчитаем метки этих вершин:
B[sub]5[/sub] = min{B[sub]2[/sub]+c[sub]25[/sub], B[sub]4[/sub]+c[sub]45[/sub], B[sub]7[/sub]+c[sub]75[/sub], B[sub]8[/sub]+c[sub]85[/sub]} = min{[$8734$]+7, [$8734$]+4, [$8734$]+2, 0+3} = min{[$8734$], [$8734$], [$8734$], 3} = 3
B[sub]7[/sub] = min{B[sub]4[/sub]+c[sub]47[/sub], B[sub]5[/sub]+c[sub]57[/sub], B[sub]6[/sub]+c[sub]67[/sub], B[sub]8[/sub]+c[sub]87[/sub], B[sub]9[/sub]+c[sub]97[/sub], B[sub]10[/sub]+c[sub]10,7[/sub]} = min{[$8734$]+9, [$8734$]+2, [$8734$]+3, 0+7, [$8734$]+8, [$8734$]+4} = min{[$8734$], [$8734$], [$8734$], 7, [$8734$], [$8734$]} = 7
B[sub]10[/sub] = min{B[sub]7[/sub]+c[sub]7,10[/sub], B[sub]8[/sub]+c[sub]8,10[/sub], B[sub]9[/sub]+c[sub]9,10[/sub]} = min{[$8734$]+4, 0+5, [$8734$]+2} = min{[$8734$], 5, [$8734$]} = 5
min{B[sub]5[/sub], B[sub]7[/sub], B[sub]10[/sub]} = min{3, 7, 5} = 3
Вершина 5 получает постоянную метку:
B[sub]5[/sub][sup]*[/sup] = 3, B[sub]7[/sub] = 7, B[sub]8[/sub][sup]*[/sup] = 0, B[sub]10[/sub] = 5, B[sub]1[/sub] = B[sub]2[/sub] = B[sub]3[/sub] = B[sub]4[/sub] = B[sub]6[/sub] = B[sub]9[/sub] = [$8734$]

2. Смежными с вершиной 5 являются вершины 2, 4, 7 и 8. Метка вершины 8 постоянна, пересчитаем метки вершин 2, 4 и 7:
B[sub]2[/sub] = min{B[sub]1[/sub]+c[sub]12[/sub], B[sub]4[/sub]+c[sub]42[/sub], B[sub]5[/sub]+c[sub]52[/sub]} = min{[$8734$]+1, [$8734$]+6, 3+7} = min{[$8734$], [$8734$], 10} = 10
B[sub]4[/sub] = min{B[sub]1[/sub]+c[sub]14[/sub], B[sub]2[/sub]+c[sub]24[/sub], B[sub]3[/sub]+c[sub]34[/sub], B[sub]5[/sub]+c[sub]54[/sub], B[sub]6[/sub]+c[sub]64[/sub], B[sub]7[/sub]+c[sub]74[/sub]} = min{[$8734$]+5, [$8734$]+6, [$8734$]+8, 3+4, [$8734$]+5, 7+9} = min{[$8734$], [$8734$], [$8734$], 7, [$8734$], 16} = 7
B[sub]7[/sub] = min{B[sub]4[/sub]+c[sub]47[/sub], B[sub]5[/sub]+c[sub]57[/sub], B[sub]6[/sub]+c[sub]67[/sub], B[sub]8[/sub]+c[sub]87[/sub], B[sub]9[/sub]+c[sub]97[/sub], B[sub]10[/sub]+c[sub]10,7[/sub]} = min{[$8734$]+9, 3+2, [$8734$]+3, 0+7, [$8734$]+8, 5+4} = min{[$8734$], 5, [$8734$], 7, [$8734$], 9} = 5
min{B[sub]2[/sub], B[sub]4[/sub], B[sub]7[/sub]} = min{10, 7, 5} = 5
Вершина 7 получает постоянную метку:
B[sub]2[/sub] = 10, B[sub]4[/sub] = 7, B[sub]5[/sub][sup]*[/sup] = 3, B[sub]7[/sub][sup]*[/sup] = 5, B[sub]8[/sub][sup]*[/sup] = 0, B[sub]10[/sub] = 5, B[sub]1[/sub] = B[sub]3[/sub] = B[sub]6[/sub] = B[sub]9[/sub] = [$8734$]

3. Смежными с вершиной 7 являются вершины 4, 5, 6, 8, 9 и 10. Метки вершин 5 и 8 постоянны, пересчитаем метки вершин 4, 6, 9 и 10:
B[sub]4[/sub] = min{B[sub]1[/sub]+c[sub]14[/sub], B[sub]2[/sub]+c[sub]24[/sub], B[sub]3[/sub]+c[sub]34[/sub], B[sub]5[/sub]+c[sub]54[/sub], B[sub]6[/sub]+c[sub]64[/sub], B[sub]7[/sub]+c[sub]74[/sub]} = min{[$8734$]+5, 10+6, [$8734$]+8, 3+4, [$8734$]+5, 5+9} = min{[$8734$], 16, [$8734$], 7, [$8734$], 14} = 7
B[sub]6[/sub] = min{B[sub]3[/sub]+c[sub]36[/sub], B[sub]4[/sub]+c[sub]46[/sub], B[sub]7[/sub]+c[sub]76[/sub], B[sub]9[/sub]+c[sub]96[/sub]} = min{[$8734$]+4, 7+5, 5+3, [$8734$]+6} = min{[$8734$], 12, 8, [$8734$]} = 8
B[sub]9[/sub] = min{B[sub]6[/sub]+c[sub]69[/sub], B[sub]7[/sub]+c[sub]79[/sub], B[sub]10[/sub]+c[sub]10,9[/sub]} = min{[$8734$]+6, 5+8, 5+2} = min{[$8734$], 13, 7} = 7
B[sub]10[/sub] = min{B[sub]7[/sub]+c[sub]7,10[/sub], B[sub]8[/sub]+c[sub]8,10[/sub], B[sub]9[/sub]+c[sub]9,10[/sub]} = min{5+4, 0+5, 5+2} = min{9, 5, 7} = 5
min{B[sub]4[/sub], B[sub]6[/sub], B[sub]9[/sub], B[sub]10[/sub]} = min{7, 8, 7, 5} = 5
Вершина 10 получает постоянную метку:
B[sub]2[/sub] = 10, B[sub]4[/sub] = 7, B[sub]5[/sub][sup]*[/sup] = 3, B[sub]6[/sub] = 8, B[sub]7[/sub][sup]*[/sup] = 5, B[sub]8[/sub][sup]*[/sup] = 0, B[sub]9[/sub] = 7, B[sub]10[/sub][sup]*[/sup] = 5, B[sub]1[/sub] = B[sub]3[/sub] = [$8734$]

4. Смежными с вершиной 10 являются вершины 7, 8 и 9. Метки вершин 7 и 8 постоянны, пересчитаем метку вершины 9:
B[sub]9[/sub] = min{B[sub]6[/sub]+c[sub]69[/sub], B[sub]7[/sub]+c[sub]79[/sub], B[sub]10[/sub]+c[sub]10,9[/sub]} = min{8+6, 5+8, 5+2} = min{14, 13, 7} = 7
Вершина 9 получает постоянную метку:
B[sub]2[/sub] = 10, B[sub]4[/sub] = 7, B[sub]5[/sub][sup]*[/sup] = 3, B[sub]6[/sub] = 8, B[sub]7[/sub][sup]*[/sup] = 5, B[sub]8[/sub][sup]*[/sup] = 0, B[sub]9[/sub][sup]*[/sup] = 7, B[sub]10[/sub][sup]*[/sup] = 5, B[sub]1[/sub] = B[sub]3[/sub] = [$8734$]

5. Смежными с вершиной 9 являются вершины 6, 7 и 10. Метки вершин 7 и 10 постоянны, пересчитаем метку вершины 6:
B[sub]6[/sub] = min{B[sub]3[/sub]+c[sub]36[/sub], B[sub]4[/sub]+c[sub]46[/sub], B[sub]7[/sub]+c[sub]76[/sub], B[sub]9[/sub]+c[sub]96[/sub]} = min{[$8734$]+4, 7+5, 5+3, 7+6} = min{[$8734$], 12, 8, 13} = 8
Вершина 6 получает постоянную метку:
B[sub]2[/sub] = 10, B[sub]4[/sub] = 7, B[sub]5[/sub][sup]*[/sup] = 3, B[sub]6[/sub][sup]*[/sup] = 8, B[sub]7[/sub][sup]*[/sup] = 5, B[sub]8[/sub][sup]*[/sup] = 0, B[sub]9[/sub][sup]*[/sup] = 7, B[sub]10[/sub][sup]*[/sup] = 5, B[sub]1[/sub] = B[sub]3[/sub] = [$8734$]

6. Смежными с вершиной 6 являются вершины 3, 4, 7 и 9. Метки вершин 7 и 9 постоянны, пересчитаем метки вершин 3 и 4:
B[sub]3[/sub] = min{B[sub]1[/sub]+c[sub]13[/sub], B[sub]4[/sub]+c[sub]43[/sub], B[sub]6[/sub]+c[sub]63[/sub]} = min{[$8734$]+3, 7+8, 8+4} = min{[$8734$], 15, 12} = 12
B[sub]4[/sub] = min{B[sub]1[/sub]+c[sub]14[/sub], B[sub]2[/sub]+c[sub]24[/sub], B[sub]3[/sub]+c[sub]34[/sub], B[sub]5[/sub]+c[sub]54[/sub], B[sub]6[/sub]+c[sub]64[/sub], B[sub]7[/sub]+c[sub]74[/sub]} = min{[$8734$]+5, 10+6, [$8734$]+8, 3+4, 8+5, 5+9} = min{[$8734$], 16, [$8734$], 7, 13, 14} = 7
min{B[sub]3[/sub], B[sub]4[/sub]} = min{12, 7} = 7
Вершина 4 получает постоянную метку:
B[sub]2[/sub] = 10, B[sub]3[/sub] = 12, B[sub]4[/sub][sup]*[/sup] = 7, B[sub]5[/sub][sup]*[/sup] = 3, B[sub]6[/sub][sup]*[/sup] = 8, B[sub]7[/sub][sup]*[/sup] = 5, B[sub]8[/sub][sup]*[/sup] = 0, B[sub]9[/sub][sup]*[/sup] = 7, B[sub]10[/sub][sup]*[/sup] = 5, B[sub]1[/sub] = [$8734$]

7. Смежными с вершиной 4 являются вершины 1, 2, 3, 5, 6 и 7. Метки вершин 5, 6 и 7 постоянны, пересчитаем метки вершин 1, 2 и 3:
B[sub]1[/sub] = min{B[sub]2[/sub]+c[sub]21[/sub], B[sub]3[/sub]+c[sub]31[/sub], B[sub]4[/sub]+c[sub]41[/sub]} = min{10+1, 12+3, 7+5} = min{11, 15, 12} = 11
B[sub]2[/sub] = min{B[sub]1[/sub]+c[sub]12[/sub], B[sub]4[/sub]+c[sub]42[/sub], B[sub]5[/sub]+c[sub]52[/sub]} = min{[$8734$]+1, 7+6, 3+7} = min{[$8734$], 13, 10} = 10
B[sub]3[/sub] = min{B[sub]1[/sub]+c[sub]13[/sub], B[sub]4[/sub]+c[sub]43[/sub], B[sub]6[/sub]+c[sub]63[/sub]} = min{[$8734$]+3, 7+8, 8+4} = min{[$8734$], 15, 12} = 12
min{B[sub]1[/sub], B[sub]2[/sub], B[sub]3[/sub]} = min{11, 10, 12} = 10
Вершина 2 получает постоянную метку:
B[sub]1[/sub] = 11, B[sub]2[/sub][sup]*[/sup] = 10, B[sub]3[/sub] = 12, B[sub]4[/sub][sup]*[/sup] = 7, B[sub]5[/sub][sup]*[/sup] = 3, B[sub]6[/sub][sup]*[/sup] = 8, B[sub]7[/sub][sup]*[/sup] = 5, B[sub]8[/sub][sup]*[/sup] = 0, B[sub]9[/sub][sup]*[/sup] = 7, B[sub]10[/sub][sup]*[/sup] = 5

8. Смежными с вершиной 2 являются вершины 1, 4 и 5. Метка вершины 2 постоянна, пересчитаем метки вершин 1 и 3:
B[sub]1[/sub] = min{B[sub]2[/sub]+c[sub]21[/sub], B[sub]3[/sub]+c[sub]31[/sub], B[sub]4[/sub]+c[sub]41[/sub]} = min{10+1, 12+3, 7+5} = min{11, 15, 12} = 11
B[sub]3[/sub] = min{B[sub]1[/sub]+c[sub]13[/sub], B[sub]4[/sub]+c[sub]43[/sub], B[sub]6[/sub]+c[sub]63[/sub]} = min{11+3, 7+8, 8+4} = min{14, 15, 12} = 12
min{B[sub]1[/sub], B[sub]3[/sub]} = min{11, 12} = 11
Вершина 1 получает постоянную метку:
B[sub]1[/sub][sup]*[/sup] = 11, B[sub]2[/sub][sup]*[/sup] = 10, B[sub]3[/sub] = 12, B[sub]4[/sub][sup]*[/sup] = 7, B[sub]5[/sub][sup]*[/sup] = 3, B[sub]6[/sub][sup]*[/sup] = 8, B[sub]7[/sub][sup]*[/sup] = 5, B[sub]8[/sub][sup]*[/sup] = 0, B[sub]9[/sub][sup]*[/sup] = 7, B[sub]10[/sub][sup]*[/sup] = 5

9. Смежными с вершиной 1 являются вершины 2, 3 и 4. Метки вершин 2 и 4 постоянна, пересчитаем метку вершины 3:
B[sub]3[/sub] = min{B[sub]1[/sub]+c[sub]13[/sub], B[sub]4[/sub]+c[sub]43[/sub], B[sub]6[/sub]+c[sub]63[/sub]} = min{11+3, 7+8, 8+4} = min{14, 15, 12} = 12
Вершина 3 получает постоянную метку:
B[sub]1[/sub][sup]*[/sup] = 11, B[sub]2[/sub][sup]*[/sup] = 10, B[sub]3[/sub][sup]*[/sup] = 12, B[sub]4[/sub][sup]*[/sup] = 7, B[sub]5[/sub][sup]*[/sup] = 3, B[sub]6[/sub][sup]*[/sup] = 8, B[sub]7[/sub][sup]*[/sup] = 5, B[sub]8[/sub][sup]*[/sup] = 0, B[sub]9[/sub][sup]*[/sup] = 7, B[sub]10[/sub][sup]*[/sup] = 5

Вершин, не имеющих постоянной метки нет, следовательно, алгоритм завершён. Кратчайший путь от вершины 8 до вершины 3 равен c[sub]85[/sub] + c[sub]57[/sub] + c[sub]76[/sub] + c[sub]63[/sub] = 3 + 2 + 3 + 5 = 12 = B[sub]3[/sub]