Нахождение кратчайшего пути в графе. Алгоритм Дейкстры 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
  • Отчет
Похожие работы
Другие работы автора
Купить

990,00 

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

После оплаты Вы получите работу на электронную почту.
DijkstraWayFinder.rar
254740
Оцени работу

рейтинг

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

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

Artyom987

/ /

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

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

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