Курсовая работа: Поиск кратчайших путей в графе методом динамического программирования

2.3. Иллюстрация алгоритма на примере графа

Найдем наикратчайший путь между вершинами 1 и 6.

1. Создаем таблицу путей, где столбцы обозначают вершины, а строки количество вершин в пути до заданной вершины. В пересечении запишем наименьшее значение текущего пути до соответствующей вершины. Начальную вершину обозначим как 0, а расстояние до остальных ?.

Таб. 2. Матрица смежности вершин на стадии инициализации графа.

2. Проверяем вершину 1 и инцидентные ей ребра. Из вершины 1 есть прямые пути в вершину 2 по ребру с весом -16 и вершину 3 по ребру с весом 13. Расстояние до остальных вершин остается равным ?, потому что из вершины 1 нет прямых ребер до остальных вершин. Поскольку путь 1>2 = -16 < ?, то добавим соответствующее значение в таблицу. Тот же алгоритм применяется к вершине 3: 1>3 = 13 < ?. Добавим в таблицу строку, содержащую пути, имеющие 1 ребро и веса до соответствующих вершин.

Таб. 3. Матрица смежности вершин при обработке вершины №1.

3. У вершины 1 больше нет инцидентных ребер, поэтому проверяем ребра 2 и 3. Из вершины 3 в вершину 2 есть прямой путь, содержащий ребро с весом 4. Проверяем, можно ли провести релаксацию ребра (процесс уменьшения суммы весов ребер до целевой вершины) т.к. путь в вершину 2 уже существует. Для этого из таблицы возьмем значение длины пути до вершины 3 = 13 и добавим к этому значению ребро с весом 4. Итоговая сумма больше, чем существующий путь в таблице для вершины 2: 13+4 = 15>-16, поэтому текущее значение пути для вершины 2 остается неизменным.

Проводим такую же операцию из вершины 2 в вершину 3: из вершины 2 в вершину 3 есть прямой путь, содержащий ребро с весом 10. Релаксируем ребро: 2(-16) + 10 < 3(13). Обновляем соответствующую ячейку в таблице:

Таб. 4. Матрица смежности вершин при обработке вершин №2 и №3.

Таким же образом проверяем ребра 3 >4 = -6 + 14 = 8; 2 >5 = -16 +

+ (-12) = -4.

Таб. 5. Матрица смежности вершин при обработке вершин №2 и №3.

4. Проверяем ребра смежные с вершинами 4 и 5:

5>3 = -4 + (-9) = -13 < -6, расстояние до вершины 3 = -13;

5>6 = -4 + 20 = 16 > 4.

4>5 = 8 + 7 = 13 > -4;

4>6 = 8 + (-4) = 4 < ?;

Обновим таблицу в соответствии с полученными значениями:

Таб. 6. Матрица смежности вершин при обработке вершин №4 и №5.

5. После того как получена таблица наименьших весов ребер из вершины 1 до остальных вершин, проверим еще раз все ребра на релаксацию с использованием данных из последней строчки текущей таблицы:

1>2 = -16; 1>3 = -13; 3>2 = -16; 2>3 = -13;

3>4 = -13 + 14 < 8 = 1;

2>5 = -4; 5>3 = -13; 4>5 = -4; 5>6 = 4;

4>6 = 1 + (-4) < 4 = -3;

Обновляем таблицу:

Таб. 7. Матрица смежности вершин при релаксации ребер графа.

6. Итоговая таблица содержит значения наикратчайших путей из вершины 1 до остальных вершин. Составим наикратчайший путь:

1>2>5>3>4>6. Сумма пути равна -3.

2.4 Алгоритмизация задачи

Для того что бы корректно применить алгоритм Беллмана-Форда на графе необходимо убедиться в отсутствии отрицательного цикла, при обходе которого сумма весов ребер будет меньше, чем предыдущая. Наличие такого цикла приведет к ошибке алгоритма из-за бесконечно уменьшающего пути между вершинами цикла.

Рассмотрим работу алгоритма:

1. Стартовую вершину обозначим как a и все расстояния до остальных вершин графа будут определены как бесконечные, а расстояние (a, a) = 0. Создается массив dist[] размера V со всеми значениями равными бесконечности, за исключением элемента dist[a].

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

3. Если после завершения цикла V-1 на следующей итерации расстояние до какой-либо вершины уменьшилось, то это означает наличие отрицательного цикла в графе. В этом случае алгоритм Беллмана-Форда возвращает сообщение о наличии такого цикла.

2.5 Разработка программы

Создаем функцию инициализации графа через матрицу смежности вершин и преобразуем в список ребер для оптимального использования алгоритма:

def get_adjacency_matrix():

    n = int(input("Введите количество вершин в графе: "))

    adj_matrix = []

    for i in range(n):

        row = list(map(int, input(f"Введите значения для вершины {i + 1}: ").split()))

        adj_matrix.append(row)

    edges = []

    for i in range(n):

        for j in range(n):

            if adj_matrix[i][j] != 0:

                edge = f"{i + 1}, {j + 1}, {adj_matrix[i][j]}"

                edges.append(edge)

    return edges

Данная функция запрашивает у пользователя размерность квадратной матрицы, построчно добавляет значения строки матрицы row в список adj_matrix. Далее матрица преобразуется в список ребер вида u, v, w, где w - значение веса ребра, инцидентного вершинам u и v.

Опишем функцию работы модифицированного алгоритма Беллмана-Форда:

from typing import List, Tuple, Union, Any

def bellman_ford_algorithm(edges: List[str], start_node: int, end_node: int) -> Union

[tuple[list[Any], list[Any]], tuple[list[int], list[float]]]:  

    inf = float("inf")

    n = len(edges)

    dist = [inf] * n

    prev = [-1] * n

    dist[start_node - 1] = 0

В данном элементе кода в функцию bellman_ford_algoritm инициализируем на вход следующие данные: стартовую вершину - start_node, конечную вершину - end_node, и список ребер - edges. Далее при помощи подключаемого модуля typing проверяем входные данные. Список edges должен иметь тип данных list, а стартовая и конечная вершины целочисленные значения int.

Переменная inf равна бесконечности и используется для инициализации списка dist, который содержит текущее кратчайшее расстояние от начальной вершины до каждой вершины в графе. Список prev инициализируется нулями и будет использоваться для хранения предыдущих вершин на кратчайшем пути.

Код последней строки dist[start_node - 1] = 0 устанавливает начальное расстояние до начального узла (список dist индексируется с 0, поэтому мы вычитаем 1 из start_node). Таким образом, мы можем начать поиск кратчайшего пути от начального узла и обновлять расстояние до остальных узлов по мере прохождения алгоритма Беллмана-Форда.

    for i in range(n - 1):

        for j in range(n):

            u, v, w = map(int, edges[j].split(","))

            if dist[u - 1] + w < dist[v - 1]:

                dist[v - 1] = dist[u - 1] + w

                prev[v - 1] = u - 1

Следующим шагом на каждой итерации алгоритма длины присвоим переменным u, v и w значения из списка edges при помощи оператора map, который позволяет присваивать переменным соответствующие входные значения, где u и v - номера вершин, соединенных ребром, а w - вес ребра. Инструкция for i in range(n-1) означает, что алгоритм будет проходить n-1 раз, так как кратчайший путь между двумя вершинами может содержать не более n-1 ребер. Инструкция for j in range(n) перебирает все ребра в графе на каждом шаге итерации.

Условие if dist[u - 1] + w < dist[v - 1] проверяет, можно ли улучшить текущий кратчайший путь от начальной вершины до вершины v через ребро (u, v) с учетом веса w. Если условие выполняется, то значения в массивах dist и prev обновляются, что дает новый кратчайший путь от начальной вершины до вершины v.

    for j in range(n):

        u, v, w = map(int, edges[j].split(","))

        if dist[u - 1] + w < dist[v - 1]:

            path = [end_node]

            node = prev[end_node - 1]

            while node != -1 and node not in path:

                path.append(node + 1)

                node = prev[node]

            path.append(node + 1)

            return list(reversed(path)), [dist[end_node-1]], True

    path = []

    node = end_node - 1

    while node != -1:

        path.append(node + 1)

        node = prev[node]

    return list(reversed(path)), [dist[end_node-1]], False

После того как все ребра в графе были рассмотрены, удостоверимся в отсутствии отрицательного цикла. Для этого снова проверяем список edges на наличие более короткого пути до вершины v, чем уже найденное значение в списке dist. Если такой путь существует, то функция возвращает в последнем значении True, которое используется для соответствующего сообщения о наличии отрицательного цикла. В ином случае функция в последнем значении возвращает False.

Независимо от наличия отрицательного цикла, функция возвращает список dist и отсортированный в обратном порядке список path, так как заполнение последнего списка было от конечной вершины к начальной.

def print_result(path: List[int], dist: List[int], k: bool):

    if not path:

        print("Невозможно найти путь между заданными вершинами.")

    elif k is True:

        print("В графе есть отрицательный цикл.")

    else:

        print(f"Длина кратчайшего пути: {dist[-1]}")

        print(f"Кратчайший путь: {' -> '.join(str(node) for node in path)}")

В последней функции опишем инструкцию для вывода полученного результата. В первую очередь проверим наличие пути между двумя заданными вершинами, и если он существует, то проверяется следующий блок elif, который сообщает о наличии отрицательного цикла, и если функция bellman_ford_algoritm вернула значение True в переменную k, то пользователь получит соответствующее сообщение. Последний блок else выполнится только при наличии маршрута между вершинами, тем самым вернет значения списков dist и path.

edges = get_adjacency_matrix()

start_node = int(input('Введите начальную вершину: '))

end_node = int(input('Введите конечную вершину: '))

path, dist, k = bellman_ford_algorithm(edges, start_node, end_node)

print_result(path, dist, k)

Завершающим этапом в переменные start_node и end_node запросим у пользователя стартовую и конечную вершины, далее последовательно вызовем вышеописанные функции.

2.6. Тестирование и отладка

В ходе работы алгоритма результат совпадает с полученным вручную, тем самым можно сделать вывод о корректности работы программы.

Заключение

В данной курсовой работе были изучены основы теории графов, разобраны понятия динамического программирования, способы представления графов в ЭВМ, а также алгоритмы, использующиеся в задаче поиска наикратчайшего пути, а именно алгоритмы Дейкстры и Беллмана-Форда. Был проведен сравнительный анализ актуальности использования вышеупомянутых алгоритмов при решении задачи поиска наикратчайшего пути на различных графах.

Библиографический список

1. В.Е. Алексеев, Д.В. Захарова. Теория графов. Учебное пособие. Издатель: ННГУ им. Н.И. Лобачевского, 2017 г. (дата обращения: 26.04.2023)

2. Основные понятия теории графов [Электронный ресурс] режим доступа URL: https://habr.com/ru/companies/otus/articles/568026/ (дата обращения: 19.04.2023)

3. Алгоритм Дейкстры [Электронный ресурс] режим доступа URL: https://habr.com/ru/companies/otus/articles/599621/ (дата обращения: 19.04.2023)