Нахождение кратчайшего пути в графе. Алгоритм Дейкстры C#.

     Задание

      Для того, чтобы найти кратчайший путь от одной вершины графа до другой вершины с учетом длины дороги и пошлины, применим алгоритм Дейкстры  и в качестве параметров используем S и P. Заметим, что данный алгоритм работает только для графов без рёбер отрицательного веса.

     Алгоритм нахождения кратчайшего пути:

Шаг первый: создаем массив флагов, была ли посещена конкретная вершина и создаем массив расстояний от точки s до любой другой.

Шаг второй: ставим в цикле, что все вершины не посещены и все расстояния равны бесконечности.

Шаг третий: ставим что расстояние от s до s равно 0 и ставим, что стартовая вершины была посещена и запоминаем последнюю посещенную вершину.

Шаг четвертый: проходимся по всем соседям данной вершины и запоминаем расстояние до них. Cравниваем все найденные пути и выбираем из них самый наименьший и запоминаем эту вершину для которого путь был самым наименьшим и ставим, что мы его посетили. Повторяем данный шаг с новой вершиной и найденным расстоянием до него.

Шаг пятый: сравниваем найденное расстояние до искомой точки с бесконечнстью, если оно равно значит пути нет.

Шаг шестой: восстанавливаем путь. Создаем массив вершин и добавляем конечную вершину в этот массив.

Шаг седьмой: пока не придем в начало, просматриваем все вершины. Если есть связь, то определяем вес из предыдущей вершины. Если вес совпал с рассчитанным, значит из этой вершины и был переход, запоминаем новый вес и предыдущию вершину и добавляем эту вершину в массив.

Шаг восьмой: возращаем список пути.

     Отчет содержит:

1. Цель работы

2. Задание

3. Теоретическая часть. Алгоритм нахождения кратчайшего пути.

4. Входные и выходные данные

5. Реализация

6. Анализ алгоритма

Список литературы

Присоединяйся

Зарегестрируйся с помощью социальных сетей.

Публикуй

Опиши работу, прикрепи файлы и назначь цену.

Зарабатывай

Получай пассивный доход с продажи работ.

Тебе понадобится 5 минут для публикации работы на сайте.
Похожие работы
Другие работы автора
Купить

990,00 

(без учета комиссии 3,8 %)

DijkstraWayFinder.rar
254740
Оцени работу

рейтинг

Поделись работой с друзьями

Мы не грузим циферки, чтоб ты увидел контент как можно быстрее;

Комментарии (0)

Artyom987

/ /

Оставить комментарий

Ты не можешь комментировать

Только зарегестрированые пользователи имеют возможность комментировать работы
Нахождение кратчайшего пути в графе. Алгоритм Дейкстры C#.
Для того, чтобы найти кратчайший путь от одной вершины графа до другой вершины с учетом длины дороги и пошлины, применим алгоритм Дейкстры и в качестве параметров используем S и P. Заметим, что данный алгоритм работает только для графов без рёбер отрицательного веса.
Категория: Образование
Стоимость: 990,00