Дейкстра за самый длинный путь в DAG

Я пытаюсь выяснить, возможно ли использовать алгоритм Дейкстры, чтобы найти самый длинный путь в направленном ациклическом пути. Я знаю, что невозможно найти самый длинный путь с Дейкстрой в общем графе из-за отрицательных циклов затрат. Но это должно работать в DAG, я думаю. Благодаря Google я нашел много противоречивых источников. Некоторые говорят, что это работает, а некоторые говорят, что это не работает, но я не нашел доказательства или контрпример. Может кто-нибудь указать мне на доказательство или контрпример?

Ответы на вопрос(5)

Ваш ответ на вопрос