今さらながらダイクストラを実装した@C++

Project Euler等で時々C++を使うのだが，いまだかつて，classを一度たりとも使っていないことに気がついた．

まぁ，僕は「オブジェクト指向なんてくそくらえ」な立場なので問題ないといえば問題ないが．しかし，使えるに越したことはない．

ということで練習がてらに，Graphクラスを作って，ダイクストラ法を実装した．

できあがりのダイクストラは下．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


template <class T>				// 重みの型
void dijkstra(const Graph &g,			// 入力グラフ
              const EdgeProperty<T> &weight,	// 各辺の重み（非負）
              const Vertex &s,			// 始点
              T *d,				// 始点からの最短距離
              int *p				// 最短経路木における各頂点の親
              );

template <class T>
void dijkstra(const Graph &g, const EdgeProperty<T> &weight,
              const Vertex &s, T *d, int *p) {
  const int size = g.succ.size();
  bool *f = new bool[size];
  fill_n(d, size, INT_MAX), d[s] = 0, fill_n(p, size, -1);
  typedef pair<T, int> Distance;
  priority_queue< Distance, vector<Distance>, greater<Distance> > q;
  q.push(Distance(0, s));
  while (!q.empty()) {
    int u;
    T d_u;
    tie(d_u, u) = q.top(), q.pop();
    if (f[u]) continue;
    f[u] = true;
    foreach (Vertex v, g.succ[u])
      if (d[v] > d_u + weight(u, v))
        p[v] = u, q.push(Distance(d[v] = d_u + weight(u, v), v));
  }
}

EdgePropertyは Edge → T の関数のようなもの．内部では配列かmapでデータを保持している．

枝が密なときは配列で，疎なときはmapで持てるようにした．勢いでやった．後悔はしてない．

枝自身に重みを持たせるという選択肢もあった．

しかし，グラフとは頂点集合とそれらの接続関係であり，トポロジカルなものである，数量のようなものは付加されていないと考える．

枝に重みがついたものは，ネットワークであり，グラフではないと考える．

という経緯で枝に重みは持たせないことに満場一致で決まった．それに，最小費用循環流などでは枝に流量の下限と上限という2値が必要だし．

全体

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58


/* Time-stamp:<2010-02-12 22:24:53>
 * dijkstra.cpp
 * ダイクストラ法．
 */
#include "boost/tuple/tuple.hpp"
#include <climits>
#include <queue>
#include "graph.h"

using namespace boost;

template <class T>				// 重みの型
void dijkstra(const Graph &g,			// 入力グラフ
              const EdgeProperty<T> &weight,	// 各辺の重み（非負）
              const Vertex &s,			// 始点
              T *d,				// 始点からの最短距離
              int *p				// 最短経路木における各頂点の親
              );

template <class T>
void dijkstra(const Graph &g, const EdgeProperty<T> &weight,
              const Vertex &s, T *d, int *p) {
  const int size = g.succ.size();
  bool *f = new bool[size];
  fill_n(d, size, INT_MAX), d[s] = 0, fill_n(p, size, -1);
  typedef pair<T, int> Distance;
  priority_queue< Distance, vector<Distance>, greater<Distance> > q;
  q.push(Distance(0, s));
  while (!q.empty()) {
    int u;
    T d_u;
    tie(d_u, u) = q.top(), q.pop();
    if (f[u]) continue;
    f[u] = true;
    foreach (Vertex v, g.succ[u])
      if (d[v] > d_u + weight(u, v))
        p[v] = u, q.push(Distance(d[v] = d_u + weight(u, v), v));
  }
}

int main () {
  typedef int Weight;
  const int n = 4;
  Graph g = Graph(n);
  EdgeProperty<Weight> weight;
  weight[g.add_edge(0, 1)] = 4;
  weight[g.add_edge(0, 2)] = 1;
  weight[g.add_edge(1, 3)] = 1;
  weight[g.add_edge(2, 1)] = 1;
  weight[g.add_edge(2, 3)] = 5;

  cout << g << endl;
  Weight *dist = new Weight[n];
  int *prev = new int[n];
  dijkstra<Weight>(g, weight, 0, dist, prev);
  for (int i = 0; i < n; ++i)
    cout << i << ": " << dist[i] << ", from " << prev[i] << endl;
}

そして，graph.h

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86


/* Time-stamp:<2010-02-12 22:30:39>
 * graph.h
 */
#include <iostream>
#include <utility>
#include <vector>
#include <map>
#include <boost/foreach.hpp>
#define foreach BOOST_FOREACH

using namespace std;

typedef int Vertex;
typedef pair<Vertex, Vertex> Edge;
typedef vector<Edge> EdgeList;
typedef vector<Vertex> VertexList;
typedef vector<VertexList> AdjacencyList;

class Graph {
public:
  AdjacencyList succ, pred;
  Graph(const int &n) {
    for (int i = 0; i < n; ++i)
      succ.push_back(VertexList()), pred.push_back(VertexList());
  }
  Edge add_edge(const Vertex &tail, const Vertex &head) {
    succ[tail].push_back(head);
    pred[head].push_back(tail);
    return Edge(tail, head);
  }
  friend ostream &operator << (ostream &outs, const Graph &g) {
    const int num_vertices = g.succ.size();
    int num_edges = 0;
    for (int i = 0; i < num_vertices; ++i) {
      num_edges += g.succ[i].size();
    }
    outs << "Number of vertices: " << num_vertices << endl;
    outs << "Number of edges: " << num_edges << endl;
    outs << "Adjacency:" << endl;
    for (int i = 0; i < num_vertices; ++i) {
      outs << i << ": -> ";
      foreach (Vertex u, g.succ[i])
        outs << u << " ";
      outs << endl;
      outs << i << ": <- ";
      foreach (Vertex u, g.pred[i])
        outs << u << " ";
      outs << endl;
    }
    return outs;
  }
};

template <class T> class EdgeProperty {
private:
  int size;
public:
  T **w_array;
  map<Edge, T> w_map;
  EdgeProperty() {
    size = -1;
  }
  EdgeProperty(const int &n) {
    w_array = new T*[n];
    for (int i = 0; i < n; ++i)
      w_array[i] = new T[n];
    size = n;
  }
  T& get(const Vertex &tail, const Vertex &head) {
    if (size == -1) return w_map[Edge(tail, head)];
    else if (tail < size && head < size) return w_array[tail][head];
  }
  T& get(const Edge &e) {
    return get(e.first, e.second);
  }
  T& operator[] (const Edge &e) {
    return get(e);
  }
  T operator() (const Vertex &tail, const Vertex &head) const {
    if (size == -1) return w_map.find(Edge(tail, head))->second;
    else if (tail < size && head < size) return w_array[tail][head];
  }
  T operator() (const Edge &e) const {
    return (*this)(e.first, e.second);
  }
};

うーん．クラス作るとコードが肥大化するなぁ．

（お前の腕がないだ(ry）

コンテンツ