Вопрос № 183281: Здравствуйте! Прошу помощи в следующем вопросе: Мне надо написать программу на C++ . Задан орграф. Известны веса рёбер. Найти путь из i в j с min суммой весов рёбер. (Граф (веса) и число вершин вводить с экрана. Если можно, не исп...
Вопрос № 183281:
Здравствуйте! Прошу помощи в следующем вопросе: Мне надо написать программу на C++ .
Задан орграф. Известны веса рёбер. Найти путь из i в j с min суммой весов рёбер.
(Граф (веса) и число вершин вводить с экрана. Если можно, не использовать векторы.)
Отвечает Киселёва Алёна aka Verena (Профессор) :
Здравствуйте, sveta11115! Для решения данной задачи можно использовать алгоритм Дейкстры. Данный алгоритм накладывает, правда, некоторые ограничения, в частности, веса рёбер не могут быть отрицательными. В данном случае мы будем рекурсивно искать кратчайшие пути от вершины i до всех вершин графа, метка, которую мы поставим на вершине j и будет являться длиной кратчайшего по сумме весов пути. Если необходимо получить данные
о том, по каким рёбрам этот путь прошёл, надо будет хранить дополнительную информацию, при имеющейся реализации узнать это нельзя. При проверке учитывайте, что нумерация вершин идёт с нуля, то есть если вершины в графе три, то они будут иметь номера 0, 1, 2, а обращение к вершине 3 вызовет ошибку, потому что её не существует. Реализация основана на этом коде, только убрала векторы, добавила проверку на ориентацию ребра при его проходе и исправила небольшую ошибку (искался не минимальный путь). Проверено на Visual Studio 2005.
* Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи.
(полный список тарифов)
** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
*** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.