Кратчайший путь

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

Нами будет рассмотрен единственный алгоритм — алгоритм Дейкстры. Он представляет собой обычный обход в ширину с двумя модификациями:

• вместо множества посещённых вершин — таблица расстояний от начальной
• вместо граничной очереди — очередь с приоритетом

Напомним, что очередь с приоритетом отличается от очереди/стека тем, что:

• каждый элемент сопровождается приоритетом — элементом некоторого линейно упорядоченного множества
• операция изъятия элемента изымает элемент с наименьшим (или же наибольшим) приоритетом

Очередь с приоритетом

Эффективную очередь с приоритетом можно получить из упорядоченного мультисловаря (это когда допускается хранить множество элементов по одному ключу) или же из обычного словаря, преобразовав его в мультисловарь одним из двух способов:

• мультисловарь типа k -> v — это словарь типа k -> List v, где List v — тип списков элементов типа v
• мультисловарь типа k -> v — это словарь типа (k, int) -> v

Поясним второй способ подробнее: он интереснее первого и зачастую проще. Идея состоит в том, чтобы сопровождать каждый ключ уникальным числом. Это лишает нас операции «получить значение по ключу», но для упорядоченных словарей наличие такой операции необязательно: она отлично заменяется операцией «найти ключ не меньший, чем заданный».

Этот способ работает по той причине, что пары (в тех языках программирования, где они есть) упорядочены сначала по первой компоненте, а затем (в рамках классов равенства по первой компоненте) — по второй.

Без лишних слов Дейкстра

Возьмём стандартный обход в ширину (из прошлой главы):

std::set<int> component(Graph &g, int v) {
    std::deque<int> border{v};
    std::set<int> visited{};
    
    while (border.size() > 0) {
        int current_vertex = border.front(); border.pop_front();
        
        if (visited.count(current_vertex)) { continue; }
        
        visited.insert(current_vertex);
        
        auto n = neighbors(g,current_vertex);
        for (int i : n) { 
            if (visited.count(i) == 0) { border.push_back(i); }
        }
    }
    
    return visited;
}

и немного модифицируем:

// всё делается в предположении, что Graph означает следующее:
using Graph = std::map<int, std::map<int, double>>;

std::map<int, double> distances(Graph &f, int v) {
    std::map<std::pair<double,int>, int> border;
    border[{0,0}] = v;
    int unique = 1;
    
    std::map<int, double> visited; // таблица расстояний
    
    while (border.size() > 0) {
        // it -- "указатель" на пару вида ((расстояние,мусор),вершина)
        auto it = border.begin();
        double d = (it->first).first;
        int current_vertex = it->second;
        border.erase(it);
        
        if (visited.count(current_vertex)) { continue; }
        
        visited[current_vertex] = d;
        
        for (auto n : g[current_vertex]) {
            int neighbor = n.first;
            double edge_length = n.second;
            
            if (visited.count(neighbor) == 0) { 
                double new_d = d + edge_length;
                border[{new_d, unique++}] = neighbor; 
            }
        }
    }
    
    return visited;
}

На каждом шагу алгоритм выбирает вершину, ближайшую к обработанному множеству. Ближайшую — по путям, все рёбра которых, кроме последнего, соединяют вершины обработанного множества.

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

Ну и для полноты картины приведём код на Haskell (без импортов и тех функций, которые не относятся к сути дела):

type Vertex = Int
type Distance = Double
type Graph = Map Vertex (Map Vertex Distance)

neighbors :: Vertex -> Graph -> [(Vertex, Distance)]
neighbors i g = case Map.lookup i g of
    Nothing -> []
    Just n  -> Map.toList n

data Front = Front !Int !(Map (Distance, Int) Vertex)

frontEmpty = Front 0 Map.empty

frontPush (v,d) (Front i m) = 
    Front (i+1) (Map.insert (d,i) v m)

frontPop (Front i m) = case Map.minViewWithKey m of
    Just ( ((d,_),v), m' ) -> Just ( (v,d), Front i m' )
    Nothing -> Nothing

distances :: Vertex -> Graph -> Map Vertex Distance
distances i g = go (frontPush (i,0) frontEmpty) Map.empty
  where
    go front distances = case frontPop front of
      Nothing -> distances
      Just ( (v,d), front' )
        | v `Map.member` distances -> go front' distances
        | otherwise ->
          let distances' = Map.insert v d distances
              n = [(v,d) | (v,d) <- neighbors v g, 
                           not (v `Map.member` distances')]
              front'' = foldl' (flip frontPush) front' n
          in go front'' distances'