§ № Кратчайший путь в ориентированном графе
Найдите кратчайший путь от вершины A до вершины F в ориентированном графе. На рисунке указаны дуги и их веса: A→B — 8, A→C — 4, C→B — 3, B→D — 6, B→E — 3, C→D — 2, C→F — 10, D→E — 3, D→F — 1, E→F — 4.
Решение
Длина пути во взвешенном графе равна сумме весов входящих в него дуг. От A можно перейти в B с длиной или в C с длиной . Через C до D получаем ; путь через B до D имеет длину , поэтому для D сохраняем длину .
До B можно также дойти через C: . Это короче прямой дуги A→B длины . Из B в E получается путь длиной . Через D до E получаем , поэтому кратчайшее найденное расстояние до E равно .
Сравним все способы прийти в F по последней дуге. Через C длина равна . Через D длина равна . Через E длина равна . Наименьшее из чисел , и — . Метка D получена по дуге C→D, а метка C — по дуге A→C. Значит, восстанавливаем путь A→C→D→F и проверяем сумму: .
Ответ
A→C→D→F; длина кратчайшего пути — .
