Для заданного взвешенного графа найти кратчайший путь между заданными вершинами.

Для нахождения кратчайшего пути от вершины **a** до вершины **h** воспользуемся алгоритмом Дейкстры: 1. Начинаем с **a**: путь 0. 2. Из **a** можно попасть в: - **b** (вес 2) - **c** (вес 5) 3. Рассматриваем **b** (кратчайший путь 2). Из **b** можно попасть в: - **c**: $2 + 3 = 5$ (равно текущему пути в **c**) - **d**: $2 + 7 = 9$ 4. Рассматриваем **c** (кратчайший путь 5). Из **c** можно попасть в: - **e**: $5 + 3 = 8$ - **d**: $5 + 4 = 9$ (то же, что через b) 5. Рассматриваем **e** (кратчайший путь 8). Из **e** можно попасть в: - **g**: $8 + 5 = 13$ - **f**: $8 + 2 = 10$ 6. Рассматриваем **f** (кратчайший путь 10). Из **f** можно попасть в: - **g**: $10 + 1 = 11$ - **h**: $10 + 9 = 19$ 7. Рассматриваем **g** (кратчайший путь 11, так как $10 + 1 < 13$). Из **g** можно попасть в: - **h**: $11 + 8 = 19$ Сравниваем варианты пути в **h**: - Путь через **f**: $a \rightarrow b \rightarrow c \rightarrow e \rightarrow f \rightarrow h = 2 + 3 + 3 + 2 + 9 = 19$ - Путь через **g**: $a \rightarrow b \rightarrow c \rightarrow e \rightarrow f \rightarrow g \rightarrow h = 2 + 3 + 3 + 2 + 1 + 8 = 19$ Кратчайший путь имеет вес **19**. Возможные варианты пути: $a-b-c-e-f-h$ или $a-b-c-e-f-g-h$.