Условие задачи
Без учета ориентации, но с учетом длин ребер графа:
Найти расстояние от всех вершин графа до вершины х0 методом редукции индексов (алгоритм Дейкстры).
При определении расстояния под длиной цепи понимается сумма длин ребер, входящих в цепь.
Ответ
Каждой вершине из графа сопоставим метку минимальное известное расстояние от этой вершины до х0. Алгоритм работает пошагово на каждом шаге он посещает одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Метка самой вершины х0 полагается равной 0, метки остальных вершин бесконечности. Это отражает то, что расстояния от х0 до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.
Потяни
