Чтобы выполнить DAG кратчайший путь по алгоритму, мы должны сначала топологически отсортировать график, и на моем завтрашнем экзамене профессор сказал нам, что мы должны использовать алгоритм Кхана, чтобы выполнить топологическую сортировку.
если мы выполняем ханскую сортировку, чтобы получить топологический порядок, а граф содержит цикл (ы), то не все вершины будут присутствовать в топологически отсортированном списке. Таким образом, когда мы ослабляем все ребра, идущие от каждой вершины, мы следуем топологическому порядку. Но, поскольку не все вершины находятся в отсортированном списке, будет ли это означать, что мы никогда не ослабляем ребра, исходящие из вершин, отсутствующих в отсортированном списке?