На нашем сайте Вы сможете найти готовые курсовые и дипломные работы по программированию
Сейчас работаем

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

     Задание:

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

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

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

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

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

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

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

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

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

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

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

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

2. Задание

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

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

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

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

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

     Содержимое проекта:

Содержимое папки "DijkstraWayFinder":

     Пример кода:

   private void findWayBox_Click(object sender, EventArgs e) {
            int v1 = (int)firstVertexFindBox.Value; // получаем первую вершину
            int v2 = (int)secondVertexFindBox.Value; // получаем вторую вершину

            // запрещаем искать путь между одинаковыми вершинами
            if (v1 == v2) {
                MessageBox.Show("Нельзя искать путь между одной и той же вершиной");
                return;
            }

            List<int> way = graph.FindWay(v1, v2); // получаем путь

            // если его нет, то сообщаем об этом
            if (way == null) {
                MessageBox.Show("Путь отсутствует");
                return;
            }

            pictureBox.Image = graph.Draw(pictureBox.Width, pictureBox.Height, way); // рисуем граф с найденным путём
        }
         // если до искомой точке бесконечное расстояние, значит пути нет
            if (distance[p] == inf) {
                length = -1;
                return null;
            }

            length = distance[p];

     Содержимое архива:

  • Исходник проекта в Visual Studio
  • Отчет
Купить 2000,00 
Сразу после оплаты Вы получите работу на электронную почту. Файлы отправляются автоматически. Исходник программ Вы сможете отредактировать, как Вам нужно.
Комментарии (0)

Artyom987

/ /

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

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

Только зарегистрированые пользователи имеют возможность комментировать работы
Купить

2000,00 

Сразу после оплаты Вы получите работу на электронную почту. Файлы отправляются автоматически. Исходник программ Вы сможете отредактировать, как Вам нужно.
DijkstraWayFinder.rar
254740
Оцени работу

рейтинг

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

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