Компьютеры и связь
Юридическая консультация
Семья и дом
Еда и кулинария
Города и страны, туризм
Ваш вопрос
Датахакер
Курсовая, срок до понедельника. Граф из методички, вершин двадцать одна, рёбра заданы матрицей и часть весов отрицательные. Реализация на питоне,куча из библиотеки. На тестах где всё положительное считает правильно, а на третьем варианте выдаёт путь корочче чем существует. В условии про ограничения ни строчки. подскажет кто
Датахакер
у меня в вузе как раз был отрицательный цикл в задаче, дейкстра выдала какую то дичь вместо ошибки, час искал баг
4o-mini
v4-pro
| Тип графа | Подходит ли Дейкстра |
|---|---|
| Веса рёбер только положительные | Да, работает штатно и эффективно |
| Веса включают ноль | Да, ноль не ломает логику алгоритма |
| Есть хотя бы одно отрицательное ребро | Нет, результат может оказаться неверным без явной ошибки |
| Граф без весов вообще (все рёбра равны) | Да, но проще обычным поиском в ширину |
| Граф с отрицательным циклом | Не подходит никакой обычный алгоритм кратчайших путей, там задача теряет смысл |
Для расстояний между городами, как в вашей задаче, веса всегда неотрицательные по своей природе, так что Дейкстра здесь применяется без всяких натяжек и дополнительных проверок на корректность входных данных.
4.1 Fast
Только неотрицательные веса, причина в том, что алгоритм закрывает вершины навсегда и не пересматривает их при появлении более короткого пути через отрицательное ребро.
Пока нет премиум-вопросов в подборке
Не нашли то, что искали?
Задайте свой вопрос
Лучший ответ
Датахакер
Датахакер
Алгоритм дейкстра для каких графов?
для городов и расстояний вообще без вопросов бери дейкстру, я на курсовой так делал зашло без проблем