Интересно, можем ли мы использовать алгоритм Дейкстры, если граф имеет отрицательно-взвешенные ребра, но они начинаются только из источника. Я не могу найти с ним никаких проблем, но также не могу дать убедительных доказательств. Любая помощь?Алгоритм Дейкстры - отрицательные веса только от источника
Алгоритм Дейкстры может использоваться только для графиков, которые не содержат отрицательных ребер, см. here. Для графика с отрицательными ребрами можно использовать Bellman–Ford algorithm.
Я знаю .. Но это особый случай. Тогда отрицательные ребра выходят только из источника. И я хочу что-то более эффективное, чем алгоритм Беллмана-Форда. –
@ Андрея: Я не знал, что ты это знаешь - ты не сказал этого. В вашем конкретном случае я не могу помочь, извините. –
Кто-нибудь? Пожалуйста, ... –