Алгоритмы на графах и их приложения. Дорофеева В.И. - 32 стр.

    3 Кратчайшие пути
    3.1 Формулировка задачи нахождения кратчайшего расстояния в
терминах теории графов
     На практике часто возникает задача минимизации расстояния между дву-
мя заданными точками при условии, что существует не менее одного возмож-
ного пути. Очевидный пример – маршрут движения по городу.
     Существенным моментом в решении многих задач является нахождение
пути (маршрута) минимальной длины в графе. Например, в транспортной зада-
че, необходимо найти, кратчайший путь по дорогам в некоторой области.
     Таким образом, математически задача о поиске кратчайшего расстояния
формулируется следующим образом:
     Задача о минимальном пути. Требуется определить такую функцию ϕ(u),

u∈U, что ϕ        принимает минимальное значение.
             xN



    3.2 Алгоритм Дейкстры для нахождения минимального пути в графе

     Рассмотрим способ задания взвешенного графа, т.е. графа, каждому ребру
которого соответствует некий параметр - вес. Для определения такого графа
используется матрица весов W, размер которой n*n, где n - количество вершин
графа. При этом элемент wi j равен весу ребра, соединяющего i-ю и j-ю верши-
ны. Если такого ребра нет, то wi j полагаем равным бесконечности (на практике
это максимально число, возможное на данном языке программирования). Этот
способ задания используется, например, в алгоритмах поиска пути во взвешен-
ном графе.
     Рассмотрим поиск пути минимальной суммарной длины во взвешенном
графе с неотрицательными весами, который реализуется с помощью алгоритма
Дейкстры. Процедура находит путь минимального веса в графе G=(V,E), задан-
ном весовой матрицей W, у которой элемент wi j равен весу ребра, соединяюще-
го i-у и j-ю вершины. При этом предполагается, что все элементы wi j неотрица-

                                          32