Дискретная математика
Алгоритм основан на предписывание вершины V и T времени меток d(vt). Величина меток постепенно уменьшаться и на каждом шаге итерации одна из временных меток становится постоянной. Это означает что метка дает точную длину кратчайшего пути от начальной вершины до просматриваемой.
Шаг 1. Нач. вершины - №1 устанавливаем d(a)=0, остальные d(2) ... d(12) = бес.
П. к. d(1) - не будет меняться, пометим ее "+" - постоянная метка.
Шаг 2. min (бес.; 0 + 7 = 7) = 7;
d(6) = min(бес.; 0 + 2 = 2) = 2;
d(5) = min(бес.; 0 + 9 = 9) = 9;
в данной строке выбираем вершину с наименьшей меткой и помечаем ее знаком плюс (+).
Шаг 3. Переносим значение меток в предыдущего знака, кроме помеченного плюса (+).
Из №6 (6 - 1) (6 - 2) (6 - 5) (6 - 7) (6 - 8) - первую вершину метки мы пересчитывать не будем.
d(7) = min(бес.; 2 + 1 = 3) = 3;
d(8) = min(бес.; 2 + 6 = 8) = 8;
Шаг 4. Из №7 (7 - 6) (7 - 5) (7 - 8) (7 - 11) (7 - 12)
d(5) = min(5; 3 + 7 = 10) = 10;
d(8) = min(8; 3 + 2 = 5 ) = 5;
d(11) = min(бес.; 3 + 6 = 9) = 9;
d(12) = min(бес.; 3 + 1 = 4) = 4;
Две вершины имеют минимальные метки.
Шаг 5. Из №2 (2 - 1) (2 - 3) (2 - 4) (2 - 5) (2 - 8)
d(3) = min(бес.; 4 + 5 = 9) = 9;
d(4) = min(бес.; 4 + 4 = 8) = 8;
d(5) = min(бес.; 4 + 8 = 12) = 12;
Шаг 7. Из №5 (5 - 1) (5 - 2) (5 - 3) (5 - 4) (5 - 6) (5 - 7) (5 - 8) (5 - 9)
d(9) = min(бес.; 5 + 5 = 10) = 10;
Шаг 8. Из №8 (8 - 4) (8 + 5) (8 - 8) (8 - 9) (8 + 10)
d(9) = min(10; 5 + 6 = 11) = 11;
d(10) = min(бес.; 5 + 7 = 12) = 12;
d(11) = min(7; 5 + 8 = 13) = 13 ;
d(4) = min(8; 8 +2 = 10) = 10;
Из 4 (4 - 3) (4 - 2) (4 - 9) (4 + 8) (4 + 5)
d(9) = min(10; 8 + 4 = 12) = 12;
Шаг 10. Из №9 (9 - 4) (9 - 5) (9 - 8) (9 - 10) (9 - 11)
d(10) = min(; 10 + 4 = 14) = 14;
d(11) = min(; 10 + 4 = 14) = 14;
