読者です 読者をやめる 読者になる 読者になる

ゆとりーなの日記

日記的な事を書いて行くと思はれる

煽られたのでダイクストラっぽいのを書いた

 なんかid:chokudai先生に「ダイクストラ実装出来ないとかだらしない」とか煽られたのでアルゴリズム×ながらも適当に実装してみましたよって話です。「なんか手でやるのは(多分)出来るけどPCにやらせるの面倒じゃないですか?」とか言ったら「手でやることをそのままやらせればいいんだよ」とか言ってた気がしたので取り敢えず手でどうやったかを思い出すために波をあさって見ましたよと。
 ダイクストラ法(最短経路問題)最初はこの頁に辿りついたわけです。取り敢えずこの頁の例題の答えが正しく出せればいいかとか思ったわけですね。解説を読んでたらなんとなく去年の情報数学なんとかの記憶が思い起こされましたが、これをPCにやらせるのは結構面倒とかやっぱり思ってました。
 次に見たのがダイクストラ法ここです。スタート以外に無限を入れるってので結構思い出しました。そういえばそんなのあったなぁと。これで面倒くさい処理が一個省けるぞよということになったので、見切り発車しました。
 で、手でやるのをPCに解かせるのに面倒だと思うのが、現実をどうPCに分からせるかとかだと思うんですよね。詰まりはグラフをどう表現するかって事です。今回はもう冷静に手抜きも手抜きなんで、こんなんになりました。無限の表現も取り敢えずintの最大値ってことで甘えました。

#include <climits>
#include <algorithm>
#include <iostream>
#include <initializer_list>
#include <iterator>
#include <string>
#include <vector>

enum node_info {
  START, OTHER
};

template <typename Node>
struct next_node {
  Node *next;
  int distance;
};

class node {
 public:
  explicit node(const std::string &name, const node_info info = OTHER) 
      : info_(info), name_(name), node_(), from_(nullptr), done_(false), cost_() {}

  void add_node(node &node, const int distance) {
    node_.push_back({&node, distance});
  }

  std::vector<next_node<node>>::iterator begin() {
    return node_.begin();
  }

  std::vector<next_node<node>>::iterator end() {
    return node_.end();
  }

  void set_from(const node * const n) {
    from_ = n;
  }

  const node *from() const {
    return from_;
  }

  node_info info() const {
    return info_;
  }

  std::string name() const {
    return name_;
  }

  void done() {
    done_ = true;
  }

  bool is_done() const {
    return done_;
  }

  void set_cost(const int cost) {
    cost_ = cost;
  }

  int cost() const {
    return cost_;
  }

 private:
  node_info info_;
  std::string name_;
  std::vector<next_node<node>> node_;
  const node *from_;
  bool done_;
  int cost_;
} null_node("null");

void connect_node(node &left, node &right, const int distance) {
  left.add_node(right, distance);
  right.add_node(left, distance);
}

class graph {
 public:
  explicit graph(std::initializer_list<node *> node_list) : node_list_() {
    node_list_.reserve(node_list.size());
    std::transform(node_list.begin(), node_list.end(), std::back_inserter(node_list_), [](node * const n) {
      if (n->info() == START) {
        n->set_cost(0);
        n->set_from(&null_node);
        n->done();
      } else {
        n->set_cost(INT_MAX);
      }
      return n;
    });
    calc();
  }

  void print_result() const {
    std::for_each(result_list_.begin(), result_list_.end(), [](const node *n) {
      std::cout << n->name() << std::endl;
      std::cout << "root: " << n->name();
      for (auto i = n; i->from()->name() != "null"; i = i->from()) {
        std::cout << " >> ";
        std::cout << i->from()->name();
      }
      std::cout << std::endl;
      std::cout << "distance: " << n->cost() << std::endl;
    });
  }

 private:
  void calc() {
    const auto start = std::find_if(node_list_.begin(), node_list_.end(), [](const node *n) {
      return n->info() == START;
    });
    for (auto it = start; it != node_list_.end() && (*it)->cost() != INT_MAX; ) {
      std::for_each((*it)->begin(), (*it)->end(), [&it, &node_list_](next_node<node> &n) {
        if (!n.next->is_done()) {
          const bool is_update = (*it)->cost() + n.distance > n.next->cost();
          n.next->set_from(is_update ? n.next->from() : (*it));
          n.next->set_cost(is_update ? n.next->cost() : (*it)->cost() + n.distance);
        }
      });
      result_list_.push_back(*it);
      node_list_.erase(it);
      it = std::min_element(node_list_.begin(), 
                            node_list_.end(),
                            [](const node *lhs, const node *rhs) {
        return lhs->cost() < rhs->cost();
      });
      (*it)->done();
    }    
  }

  std::vector<node *> node_list_;
  std::vector<node *> result_list_;
};

int main() {
  node start("start", START);
  node point1("p1");
  node point2("p2");
  node point3("p3");
  node point4("p4");
  node point5("p5");
  connect_node(start, point1, 5);
  connect_node(start, point2, 4);
  connect_node(start, point3, 2);
  connect_node(point1, point5, 6);
  connect_node(point1, point2, 2);
  connect_node(point2, point3, 3);
  connect_node(point2, point4, 2);
  connect_node(point3, point4, 6);
  connect_node(point4, point5, 4);
  graph g({&start, &point1, &point2, &point3, &point4, &point5});
  g.print_result();
  int i;
  std::cin >> i;
  return 0;
}

出力

start
root: start
distance: 0
p3
root: p3 >> start
distance: 2
p2
root: p2 >> start
distance: 4
p1
root: p1 >> start
distance: 5
p4
root: p4 >> p2 >> start
distance: 6
p5
root: p5 >> p4 >> p2 >> start
distance: 10

あれだけスマポスマポとか言っときながら生ポ使ったりして悪さしてますが、まぁそんなことはどうでもいいんです。何故ならダイクストラ法をやってくれるBoost.Graphという素敵なライブラリが存在しているので、普通にそちらを使えばいいんです。