Алгоритм Дейкстры

Задача

Дан граф $G=(V, E)$ (возможно, ориентированный), все рёбра которого имеют неотрицательный вес. В $G$ выделена вершина $s$ и нужно найти кратчайшие расстояния от $s$ до всех вершин в графе.

Лемма

Разобьём $|V|$ на $2$ множества: $visited$ $~-$ содержащее $start$ $~-$ и $V \setminus visited$. Пусть для всех вершин в $visited$ мы уже посчитали кратчайшие расстояния. Рассмотрим среди вершин из $V \setminus visited$ только те, которые соединены ребром хотя бы с одной из вершин $visited$. Теперь выберем из оставшихся вершин в $V \setminus visited$ такую $u$, для которой величина, равная $\min_{v, v \in In(u)} \rho (s, v) + w(v, u)$ минимальна. Тогда для $u$ верно, что $\rho(s, u) = \min_{v, v \in In(u)} \rho (s, v) + w(v, u)$.

Доказательство

Пусть не так. Тогда существует путь из $s$ в $u$, длина которого меньше описанной выше величины. Рассмотрим первое ребро на этом пути, начало которого ($v'$) лежит в $visited$, а конец ($u'$) $~-$ нет. Заметим тогда, что путь от $s$ до $u'$ заведомо не длиннее пути $s ~- v' - u' ~- u$, который, в свою очередь, по предположению от противного, короче пути, который рассматривается в лемме (берём для $u$ вершину $v$ и $visited$, для которой $\rho (s, v) + w(v, u)$ минимально). Но тогда вершина $u$ не минимальна в том смысле, в которой заявляется в лемме $~-$ мы нашли вершину $u'$ не из $visited$ и смежную с ней $v'$ из $visited$, для которых расстояние $s ~- v' - u'$ меньше, чем такое же для $u$. Противоречие.

Описание алгоритма

• В начале $dist[s] = 0$, $dist[ V \setminus \{s\}] = INF$
• На каждом шаге алгоритма мы выбираем из ещё не рассмотренных вершин минимальную в смысле леммы выше. Для этого мы, добавляя в $visited$ очередную вершину, просматриваем всех её соседей и улучшаем для каждого из них оценку сверху на длину кратчайшего пути
• Заканчиваем алгоритм мы через |V| итераций.

Как брать минимальную вершину?

Это можно делать двумя способами:

1. Каждый раз заново перебирать все вершины и брать минимальную. В таком случае сложность алгоритма становится $O(\underbrace{V^2}_\text{на каждой из V итераций рассматриваем все вершины} + \underbrace{E}_\text{суммарно на всех шагах мы рассмотрим каждое ребро по 2 раза})$.
2. Поддерживать отсортированный список пар (например, с помощью std::set) вида (dist[v], v), где в dist[v] хранится текущая оценка сверху на минимальное расстояние. В этом случае сложность алгоритма будет $O(\underbrace{ElogV}_\text{суммарно на всех шагах мы прорелаксируем все рёбра} + \underbrace{VlogV}_\text{на каждой итерации мы извлекаем вершину из set'а}) = O((V+E)logV)$

Реализация

За $V^2 + E$

typedef int Vertex;
typedef long long dist_t;
                             
vector<dist_t>
ShortestDistancesDijkstra(vector<vector<int> >& adjacent, /* граф, хранимый списками смежности */
                                         Vertex start) {
  int n = adjacent.size();
  vector<dist_t> dist(n, INF);
  dist[start] = 0LL;
  
  vector<bool> is_visited(n, false);

  for (int iter_n = 0; iter_n < n; ++iter_n) {
    // ============== Выбираем ближайшую непосещённую ==============
    
    Vertex closest_not_visited = -1;
    dist_t closest_dist = INF;

    for (Vertex v = 0; v < n; ++v) {
      if (!is_visited[v] && dist[v] < closest_dist) {
        closest_dist = dist[v];
        closest_not_visited = v;
      }  
    }
    
    is_visited[closest_not_visited] = true;

    // ============== Релаксируем рёбра, идущие из неё ==============

    for (auto&& [to, w] : adjacent[closest_not_visited]) {
      dist[to] = min(dist[to], dist[closest_not_visited] + w;
    }
  }

  return dist;
}

За $(E+V)logV$

typedef int Vertex;
typedef long long dist_t;
              
vector<dist_t>
ShortestDistancesDijkstra(vector<vector<int> >& adjacent, /* граф, хранимый списками смежности */
                                         Vertex start) {
  int n = adjacent.size();
  vector<dist_t> dist(n, INF);
  dist[start] = 0LL;
  
  set<pair<dist_t        /* dist[v] */,
           Vertex        /* v */ >
     > not_visited_dist;

  for (Vertex v = 0; v < n; ++v) {
    not_visited.insert({dist[v], v});
  }
  
  while (!not_visited_dist.empty()) {
    // ============== Выбираем ближайшую непосещённую ==============

    auto&& [closest_d, closest_not_visited] = *not_visited_dist.begin();
    not_visited_dist.erase(begin);

    // ============== Релаксация рёбер из неё ==============

    for (auto&& [to, w] : adjacent[closest_not_visited]) {
      if (dist[to] > dist[closest_not_visited] + w) {
        not_visited_dist.erase({dist[to], to});
        dist[to] = dist[closest_v] + w;
        not_visited_dist.insert({dist[to], to});
      }
    }
  }

  return dist;
}

---

Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex