メモの日々

■ [dev][c++] 単一始点最短経路問題の解法

最短経路問題を解く幅優先探索とダイクストラ法をメモ。

幅優先探索

すべての辺の重みが等しいグラフに対する単一始点最短経路問題は幅優先探索で効率よく解ける。幅優先探索はキューを使って始点に近い頂点から順に経路の重みを決定していくように実装すればよい。

Aizu Online Judgeに幅優先探索の問題があるのでこれを解くC++コードをメモ。

#include <iostream>
#include <queue>
#include <vector>

struct node
{
  int name;
  std::vector<node*> neighbors;
  int distance_from_root{-1};
};

void solve(std::vector<node>& nodes)
{
  std::queue<node*> queue;
  auto& root = nodes.front();
  root.distance_from_root = 0;
  queue.push(&root);

  while (!queue.empty()) {
    auto* target = queue.front();
    queue.pop();

    for (auto* n : target->neighbors) {
      if (n->distance_from_root >= 0) continue;
      n->distance_from_root = target->distance_from_root + 1;
      queue.push(n);
    }
  }
}

int main()
{
  int n;
  std::cin >> n;

  std::vector<node> nodes(n);
  for (int i = 0; i < n; ++i) {
    int u, k;
    std::cin >> u >> k;
    auto& node = nodes.at(u - 1);
    node.name = u;
    node.neighbors.resize(k);
    for (auto& nb : node.neighbors) {
      int v;
      std::cin >> v;
      nb = &nodes.at(v - 1);
    }
  }

  solve(nodes);

  for (const auto& node : nodes) {
    std::cout << node.name << ' ' << node.distance_from_root << std::endl;
  }
}

ダイクストラ法

辺の重みが非負のグラフに対する単一始点最短経路問題にはダイクストラ法がシンプルで効率が良い。

ダイクストラ法は幅優先探索と似たコードで実装できる。キューの代わりに優先度付きキューを使い、「経路の重みの小さい頂点から辿れる頂点」から順に経路の重みを決定していくようにする。

同じくAizu Online Judgeの単一始点最短経路の問題を解くコードをメモ。

#include <iostream>
#include <limits>
#include <queue>
#include <vector>

template<typename D>
struct link
{
  D destination;
  int length;
};

struct node
{
  int name;
  std::vector<link<node*>> links;
  int distance_from_root{std::numeric_limits<int>::max()};
};

void solve(std::vector<node>& nodes, node& root)
{
  auto queue_compare = [](const node* lhs, const node* rhs) {
    return lhs->distance_from_root > rhs->distance_from_root;
  };
  std::priority_queue<
      node*,
      std::vector<node*>,
      decltype(queue_compare)
  > queue{queue_compare};

  root.distance_from_root = 0;
  queue.push(&root);

  while (!queue.empty()) {
    auto* target = queue.top();
    queue.pop();

    for (const auto& link : target->links) {
      auto* neighbor = link.destination;
      const auto d = target->distance_from_root + link.length;
      if (neighbor->distance_from_root <= d) continue;
      neighbor->distance_from_root = d;
      queue.push(neighbor);
    }
  }
}

std::string distance_string(int distance)
{
  return distance == std::numeric_limits<int>::max()
      ? "INF"
      : std::to_string(distance);
}

int main()
{
  int node_count, link_count, root_name;
  std::cin >> node_count >> link_count >> root_name;

  std::vector<node> nodes(node_count);
  for (int i = 0; i < link_count; ++i) {
    int s, t, d;
    std::cin >> s >> t >> d;
    auto& n = nodes.at(s);
    n.name = s;
    n.links.push_back(link<node*>{&nodes.at(t), d});
  }

  solve(nodes, nodes.at(root_name));

  for (const auto& n : nodes) {
    std::cout << distance_string(n.distance_from_root) << std::endl;
  }
}