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

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

12
задан punkyduck 6 November 2011 в 15:21
поделиться