2. グラフ関係のアルゴリズム

ここでは最短経路問題を始めとするグラフ関係のアルゴリズムを紹介する。

2.1. ダイクストラ法

ダイクストラ法を用いれば負の辺を含まない単一始点最短経路問題を解くことが出来る。

ダイクストラ法では、未確定ノードの暫定コストが最小のものを順次確定させていく。暫定コストの更新は確定ノードが増えるごとにそれに隣接するノードについて確定ノードのコスト+辺のコストで更新される。ただし、それが元の暫定コストよりも小さいときに限る。

プライオリティキューを用いて実装出来る。暫定コストの更新があった段階でプライオリティキューにプッシュする。

#include <iostream>
#include <vector>
#include <queue>
const int INF = 1e9;

struct Edge
{
	int to, cost;
};

struct Vertex
{
	int no;
	int cost;
	bool operator>(const Vertex &v) const
	{
		return this->cost > v.cost;
	}
	bool operator<(const Vertex &v) const
	{
		return this->cost < v.cost;
	}
	std::vector<Edge> e;
};

int main()
{
	int V; std::cin >> V;//頂点の数
	int E; std::cin >> E;//辺の数
	int r; std::cin >> r;//始点の頂点番号
	std::vector<Vertex> v(V);
	for(int i=0; i<V; i++)
	{
		v[i].no = i;
		v[i].cost = INF;
	}
	v[r].cost = 0;

	for(int i=0; i<E; i++)
	{
		int s; std::cin >> s;
		int t; std::cin >> t;
		int d; std::cin >> d;
		v[s].e.push_back(Edge{t,d});
	}

	std::priority_queue<Vertex, std::vector<Vertex>, std::greater<Vertex> > pq;
	pq.push(v[r]);
	while(!pq.empty())
	{
		Vertex current = pq.top(); pq.pop();
		if(v[current.no] < current) continue;
		for(auto &x: current.e)
		{
			if(v[x.to].cost > v[current.no].cost+x.cost)
			{
				v[x.to].cost = v[current.no].cost + x.to;
				pq.push(v[x.to]);
			}
		}
	}

	for(int i=0; i<V; i++)
	{
		if(v[i].cost!=INF) std::cout << v[i].cost;
		else std::cout << "INF";
		std::cout << std::endl;
	}
	return 0;
}

2.2. ベルマンフォード法

単一始点最短経路問題で負の辺を持つ場合はベルマンフォード法を用いればよい。

これはダイクストラ法よりも単純で、始点のコストをゼロにしたあと、全辺の走査を行いながら頂点の更新をひたすら行っていく手法である。

#include <iostream>
#include <vector>
const int INF = 1e9;

struct Vertex
{
	int cost;
};

struct Edge
{
	int from , to , cost;
};

int main()
{
	int V; std::cin >> V;
	int E; std::cin >> E;
	int r; std::cin >> r;

	std::vector<Edge> e;
	for(int n=0; n<E ; n++)
	{
		int s; std::cin >> s;
		int t; std::cin >> t;
		int d; std::cin >> d;
		e.push_back(Edge{s,t,d});
	}
	std::vector<Vertex> v(V);
	for(auto &x : v)
	{
		x.cost = INF;
	}

	v[r].cost = 0;
	bool update = true;
	while(update)
	{
		update = false;
		for(auto &x : e)
		{
			if(x.cost!=INF && v[x.to].cost>v[x.from].cost+x.cost)
			{
				v[x.to].cost = v[x.from].cost + x.cost;
				update = true;
			}
		}
	}


	for(int n=0 ; n<V ; n++)
	{
		if(v[n].cost!=INF) std::cout << v[n].cost;
		else std::cout << "INF";
		std::cout << std::endl;
	}
	return 0;
}

2.3. ワーシャルフロイド法

全ての二頂点間の最短経路を求めるときにはワーシャルフロイド法が使える。

これは非常に実装がシンプルである。

#include <iostream>
#include <stdio.h>
const int INF = 1e9;

int main()
{
	int V; std::cin >> V;
	int E; std::cin >> E;
	int **d = new int*[V];
	for(int i=0; i<V; i++) d[i] = new int[V];
	for(int i=0; i<V; i++)
		for(int j=0; j<V; j++)
		{
			d[i][j] = INF;
		}

	for(int i=0; i<E; i++)
	{
		int s; std::cin >> s;
		int t; std::cin >> t;
		int cost; std::cin >> cost;
		d[s][t] = d[t][s] = cost;
	}
	for(int k=0; k<V; k++)
		for(int i=0; i<V; i++)
			for(int j=0; j<V; j++)
			{
				d[i][j] = std::min(d[i][j], d[i][k]+d[k][j]);
			}
	
	for(int i=0; i<V; i++)
		for(int j=0; j<V; j++)
		{
			printf("d[%d][%d] = %d\n", i, j, d[i][j]);
		}

	for(int i=0; i<V; i++) delete[] d[i];
	delete[] d;
	return 0;
}

2.4. プリム法

最小全域木を求めるにはプリム法を使えばよい。

まず好きな頂点を一つ選び、使用済みとする。そこから出てる全てのEdgeをプラオリティキューにpushする。これが初期化。

次にプライオリティキューからpopしてそこから繋る頂点を使用済とする。そこから出てる全てのEdgeをプライオリティキューにpushする。これを繰り返す。

#include <iostream>
#include <queue>
#include <vector>
#include <numeric>

class Edge
{
	public:
		Edge(){}
		Edge(int cost, int to)
		{
			this->cost = cost;
			this->to = to;
		}
		int cost, to;
		bool operator>(const Edge &e) const
		{
			return this->cost > e.cost;
		}
};

class Vertex
{
	public:
		int no;
		std::vector<Edge> ve;
};

int main()
{
	int n; std::cin >> n;
	int a[100][100];

	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
		{
			int tmp; std::cin >> tmp;
			a[i][j] = tmp;
		}
	std::vector<Vertex> vv(n);
	for(int i=0; i<n; i++)
	{
		vv[i].no = i;
		for(int j=0; j<n; j++)
		{
			if(i!=j && a[i][j]!=-1) vv[i].ve.push_back(Edge(a[i][j],j));
		}
	}

	std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge> > q;
	for(auto &x : vv[0].ve)
	{
		q.push(x);
	}
	std::vector<bool> MST(n);
	for(int i=0; i<n; i++) MST[i] = false;
	MST[0] = true;
	std::vector<Edge> lMST;

	while(!q.empty())
	{
		Edge e;
		while(!q.empty())
		{
			e = q.top(); q.pop();
			if(MST[e.to]==false) break;
		}
		if(MST[e.to]==false)
		{
			MST[e.to] = true;
			lMST.push_back(e);
			for(auto &x : vv[e.to].ve)
			{
				q.push(x);
			}
		}
	}
	int ans = 0;
	for(auto &x : lMST)
	{
		ans += x.cost;
	}
	std::cout << ans << std::endl;

	return 0;
}