ダイクストラ法

なんか大変微妙な実装になってしまったが、有向・無向グラフを実装した。正直、使うごとに自分で定義してアルゴリズムも書き直したほうがいい気がするのでこれ以上は改良しないで色々グラフを堪能していこうと思います。

• 使用例

#include <cstdio>

#include "Graph.h"

int main() {
	Graph<int, int> g;

	auto v1 = g.createVertex(1);
	auto v2 = g.createVertex(2);
	auto v3 = g.createVertex(3);
	auto v4 = g.createVertex(4);
	auto v5 = g.createVertex(5);

	g.createEdge(v1, v2, 12);
	g.createEdge(v1, v3, 10);
	g.createEdge(v1, v4, 1);
	g.createEdge(v2, v3, 2);
	g.createEdge(v2, v5, 1);
	g.createEdge(v3, v4, 20);
	g.createEdge(v4, v5, 1);

	g.solveByDijkstra(0, INT_MAX);

	g.show();

	getchar();
	return 0;
}

• Graph.h

#pragma once

#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include "Vertex.h"
#include "Edge.h"

template <typename Data, typename CostType>
class Graph {
public:
	Graph() : vertex_size(0), edge_size(0) {

	}

	Vertex<Data> createVertex(const Data& data) {
		vertex_list.emplace_back(data, vertex_size++);
		return vertex_list.back();
	}

	void createEdge(const Vertex<Data>& from, const Vertex<Data>& to, const CostType& cost) {
		edge_list.emplace_back(from, to, cost, edge_size++);
		auto edge_id = edge_list.back().id;
		edge_list.emplace_back(to, from, cost, edge_size++);
		auto reverse_edge_id = edge_list.back().id;

		auto& v_from = vertex_list[from.id];
		auto& v_to = vertex_list[to.id];

		v_from.edge_id_list.emplace_back(edge_id);
		v_to.edge_id_list.emplace_back(reverse_edge_id);
	}

	void createEdgeTo(const Vertex<Data>& from, const Vertex<Data>& to, const CostType& cost) {
		edge_list.emplace_back(from, to, cost, edge_size++);
		auto edge_id = edge_list.back().id;

		auto& v_from = vertex_list[from.id];
		v_from.edge_id_list.emplace_back(edge_id);
	}

	void solveByDijkstra(int start, const CostType max_cost) {
		// 初期化
		std::vector<CostType> d(vertex_size);
		std::vector<int> prev(vertex_size);
		std::fill(d.begin(), d.end(), max_cost);
		std::vector<bool> is_use(vertex_size);

		std::fill(is_use.begin(), is_use.end(), false);

		struct queue_data {
			int id;
			CostType cost;
		};

		struct queue_func {
			int operator()(const queue_data& ia, const queue_data& ib) {
				return ia.cost > ib.cost;
			}
		};

		auto queue = std::priority_queue<queue_data, std::vector<queue_data>, queue_func>(queue_func());

		queue.push(queue_data { 0, 0 } );
		d[start] = 0;

		// 実行
		while(!queue.empty()) {
			const queue_data qd = queue.top();
			const int u_id = qd.id;
			is_use[u_id] = false;
			queue.pop();

			for(const auto e_id : vertex_list[u_id].edge_id_list) {
				const auto edge = edge_list[e_id];
				const CostType cost = d[u_id] + edge.cost;
				if(d[edge.to_id] > cost) {
					d[edge.to_id] = cost;
					prev[edge.to_id] = u_id;

					if(!is_use[edge.to_id]) {
						queue.push(queue_data{ edge.to_id, cost });
						is_use[edge.to_id] = true;
					}
				}
			}
		}

		for(size_t i = 0; i < prev.size(); ++i) {
			printf("%d → %d\n", vertex_list[prev[i]].data, vertex_list[i].data);
		}
	}

	void show() {
		printf("=== Vertex ===\n"); 
		for(Vertex<Data>& it : vertex_list) {
			printf("%d: %d\n", it.id, it.data);
		}
		printf("=== Edge ===\n");
		for(Edge<CostType>& it : edge_list) {
			printf("%d: %d (%d→%d)\n", it.id, it.cost, it.from_id, it.to_id);
		}
	}
private:
	std::vector<Vertex<Data>> vertex_list;
	std::vector<Edge<CostType>> edge_list;
	int vertex_size;
	int edge_size;
};

• Edge.h

#pragma once

template <typename Data, typename CostType>
class Graph;

template <typename Data>
class Vertex;

template <typename CostType>
class Edge {
	template <typename Data, typename CostType>
	friend class Graph; 
	template <typename T>
	friend class Vertex;
	
public:
	template <typename T>
	Edge(const Vertex<T>& from, const Vertex<T>& to, const CostType& cost, int id) : from_id(from.id), to_id(to.id), cost(cost), id(id) { }
private:
	CostType cost;
	int id;
	int from_id;
	int to_id;
};

• Vertex.h

#pragma once

#include <vector>

template <typename Data, typename CostType>
class Graph;

template <typename Data>
class Edge;

template <typename Data>
class Vertex {
	template <typename Data, typename CostType>
	friend class Graph;
	friend Edge<Data>;
	
public:
	Vertex(const Data& data, int id) : data(data), edge_id_list(0), id(id) { }

private:
	Data data;
	int id;
	std::vector<int> edge_id_list;
	static int max_id;
};

template <typename Data>
int Vertex<Data>::max_id = 0;