Курсовая работа: Теория графов. Алгоритм Йена

Теория графов - это раздел математики, изучающий математические объекты, представляющие собой совокупность вершин (узлов) и рёбер (связей) между этими вершинами. Графы широко применяются в различных областях науки и техники, таких как компьютерные науки, логистика, социология, транспорт и многие другие.

Одним из важных понятий в теории графов является понятие кратчайшего пути между двумя вершинами графа. Для нахождения кратчайшего пути существует множество алгоритмов, одним из которых является алгоритм Йена.

Алгоритм Йена - это модификация алгоритма Дейкстры, который позволяет находить k кратчайших путей между двумя вершинами графа. При этом алгоритм Йена эффективно использует результаты предыдущих вычислений, что уменьшает вычислительную сложность и время работы алгоритма.

Для работы алгоритма Йена необходимо предварительно найти один кратчайший путь между заданными вершинами. Затем этот путь разбивается на отрезки, называемые корректирующими дугами, после чего каждая корректирующая дуга удаляется из графа. После этого начинается поиск следующего кратчайшего пути, и так до тех пор, пока не будет найдено k кратчайших путей.

Основным преимуществом алгоритма Йена является возможность нахождения нескольких кратчайших путей между вершинами за один проход по графу. Это особенно полезно, например, при поиске оптимального маршрута в сети дорог с учётом различных критериев (расстояние, время, стоимость и т.д.).

Таким образом, алгоритм Йена является эффективным инструментом для нахождения нескольких кратчайших путей в графе и может быть применён в различных областях, где требуется оптимизация путей и передвижений.