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

Задание:

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

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

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

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

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

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

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

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

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

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

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

• Цель работы
• Задание
• Теоретическая часть. Алгоритм нахождения кратчайшего пути
• Входные и выходные данные
• Реализация
• Анализ алгоритма
• Список литературы

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

Содержимое папки "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
• Отчет (4 страницы)