Что делает: находит кратчайшие расстояния от одной вершины до всех остальных в взвешенном ациклическом ориентированном графе

Общая идея:

Релаксация рёбер в порядке топологической сортировки

Реализация:

1. Топологическая сортировка вершин графа
2. Инициализация расстояний и родителей
3. for каждой вершины в порядке топсорта
		for каждой смежной вершины
			Релаксация ребра

int main() {
	for u из G(V) do {
		u.distance = INF
		u.parent = NULL
	}
	s.distance = 0 // инициализируем стартовую вершину
	Topsort(graph) // топологически сортируем вершины графа
	for u из G(V).topsorted
		for v смежной u
			Relax(edge(u,v))
}

void Relax(edge) {
	v.distance = min(v.distance, u.distance + edge.weight)
	if v.distance changes:
		v.parent = u
}

‼ Особенности алгоритма нахождения кратчайших путей в DAG:

1. работает быстрее, но больше ограничений по графу (ориентированный и ациклический)

Визуализация: этим я займусь чуть попозже