今さらながらダイクストラを実装した@C++
12 / Feb 2010Project Euler等で時々C++を使うのだが,いまだかつて,classを一度たりとも使っていないことに気がついた.
まぁ,僕は「オブジェクト指向なんてくそくらえ」な立場なので問題ないといえば問題ないが.しかし,使えるに越したことはない.
ということで練習がてらに,Graphクラスを作って,ダイクストラ法を実装した.
できあがりのダイクストラは下.
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
枝が密なときは配列で,疎なときはmapで持てるようにした.勢いでやった.後悔はしてない.
枝自身に重みを持たせるという選択肢もあった.
しかし,グラフとは頂点集合とそれらの接続関係であり,トポロジカルなものである,数量のようなものは付加されていないと考える.
枝に重みがついたものは,ネットワークであり,グラフではないと考える.
という経緯で枝に重みは持たせないことに満場一致で決まった.それに,最小費用循環流などでは枝に流量の下限と上限という2値が必要だし.
全体
/* 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
/* 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)