メモの日々

■ [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;
  }
}

■ [tdiary] tDiaryを5.1.2へバージョンアップ

tDiaryを5.1.2へバージョンアップした。前回のバージョンアップは去年。いくつかメモ。

トップディレクトリ

• 旧バージョンから次をコピーする。
  • .htaccess
  • index.rdf
  • mimetex.xcg
  • no_comments.rdf
  • tdiary.common.conf
    • 異なるパスで動作確認する際には「@options['sp.path']」に設定しているパスを変更する必要があることに注意。
  • tdiary.conf
    • 異なるパスで動作確認する際には「@index」と最後のevalの行に設定しているパスを変更する必要があることに注意。
• index.rbとupdate.rbをそれぞれindex.cgiとupdate.cgiという名前のファイルにコピーする。スレッドメモから参照されるので.rbの方も残しておく必要がある。
• index.cgiとupdate.cgiの1行目を「#!/usr/local/bin/ruby2.6」に書き換える。このサーバにRuby 2.7は用意されていないみたい。
• 次のファイルに実行権限を付与する。
  • index.cgi
  • update.cgi
  • mimetex.xcg

プラグイン

• 旧バージョンの misc/plugin/ から次をコピーする。
  • jdate.rb
  • mathjax.rb
  • mimetex.rb
  • section_permalink.rb
  • section_permalink_anchor.rb
  • title_anchor.rb
• category-legacy.rbには独自の変更をしていたが、これをしなくても新しい順に表示されるようになっていた。ただ、動作がおかしい所もあるので後で調べる。
  • → コードに問題があったのでpull requestを送って取り込んでもらえた。
• 5.1.0リリースの説明を参考に、amazon.rbの新しい設定を行う。が、今のところ書影は表示されない。
  • → amazon.rbはどうしても動くようにできなかったので、新しいプラグインopenbd.rbを作った。

■ [dev][howto] GitのリモートURLの変更

GitのリポジトリのリモートURLの変更にはgit remote set-urlを使用する。

GitHubのヘルプにURLをHTTPSからSSHに変更する方法が書かれていてありがたい。

■ [tdiary] openBDプラグインを作った

tDiaryのAmazonプラグインがPA-API V5版になったら書影を取得できなくなってしまった。AmazonからのHTTPのレスポンスが429 Too Many Requestsエラーになってしまう。

書影を提供してくれるサービスとしてopenBDがあることを知ったので、これを使って書影を表示するプラグインを作ってみた。

この日記ではこのプラグインを使うようにしている。こんな感じ→↓ WEB+DB PRESS Vol.117
WEB+DBPRESS編集部編／著
技術評論社
1480円

が、openBDは書影を取得できない本がたくさんある感じだった。版元ドットコムにある書影データを取得できるAPIだと思うのだけれど、版元ドットコムに書影があってもopenBDでは書影を取得できない本が結構ある。これは残念。問い合わせてみたけど今のところ返事はない。

それでも、少しは書影を表示できるようになったのでよかった。