ccf認証201812-4データセンター(spfa、dijkstra、kruskal、prim多様なアルゴリズムバージョン)

文書ディレクトリ

ccf認証201812-4データセンター(spfa、dijkstra、kruskal、prim多様なアルゴリズムバージョン)

最小生成ツリー

kruskalアルゴリズム

primアルゴリズム

単一ソース最短パス

dijkstraアルゴリズム

spfaアルゴリズム

ccf認証201812-4データセンター(spfa、dijkstra、kruskal、prim多様なアルゴリズムバージョン)
この問題には2種類の解法があり,それぞれ最小生成ツリーと単源最短経路を利用する.ここで、最小生成ツリーはprimとkruskalの2つのアルゴリズムを使用することができ、単一ソースの最短パスはdijkstraとspfaの2つのアルゴリズムを使用することができる.この機会にこのいくつかの図論の基本的な、よく使われるアルゴリズムをまとめ、後でこのいくつかのアルゴリズムのテンプレートを使うときはここで取りに来ます.
最小生成ツリー
この問題の最終解は図の最小生成ツリーのn-1辺の中で重みが最も大きいもので、ネット上にはいくつかの証明方法があるが、私が見たものの中で、証明は厳密ではなく、kruskalアルゴリズムの内容と関係があるべきだと知っているだけだ.私が「アルゴリズム導論」を読んだ経験から見ると、図論のこれらの基本アルゴリズムは書きにくいわけではありませんが、本当にアルゴリズムの正確性を厳格に証明するのは難しいので、私はいっそその正確性を深く研究しないで、ここではコードを貼って、参考にしたいだけです.
kruskalアルゴリズム
私は以前kruskalアルゴリズムが実現するのは複雑だと潜在意識していたが,並列調査セットをベースにしなければならないため,並列調査セットの実現には時間がかかる.いくつかの経験を積んだ後、通常は一般的に使用され、収集され、最高効率を達成する必要はなく、経路圧縮を実現すればよいことが分かったが、これは簡単に書くことができる.従って,従来のkruskalアルゴリズムはこんなに簡単であることが分かった.結局,実装された並列調査セットに基づいて,戦略的にも実装的にも簡単である.

#include 
#include 
#include 
using namespace std;

//kruskal         
// main   ，                ，           

const int MAXV = 50010;
const int MAXE = 100010;
int n, m, root;
int fa[MAXV];

struct Edge{
	int u, v, w;
	Edge() { }
	Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w) { }
	friend bool operator<(Edge a, Edge b){
		return a.w < b.w;
	}
}edges[MAXE];

int find(int s){  //        ，        
	if (s == fa[s])
		return s;
	return fa[s] = find(fa[s]);
}

int main(){
	cin >> n >> m >> root;
	int u, v, w;
	for (int i = 1; i <= m; i++){
		cin >> edges[i].u >> edges[i].v >> edges[i].w;
	}
	sort(edges + 1, edges + 1 + m);
	for (int i = 1; i <= n; i++)
		fa[i] = i;
		
	int cnt, ans, a, b;
	Edge it; 
	cnt = ans = 0;
	for (int i = 1; i <= m; i++){
		it = edges[i];
		a = find(it.u);
		b = find(it.v);
		if (a == b)  //     ，         
			continue;
		fa[a] = b;  //             
		cnt++;  //       ，  +1 
		ans = it.w;  //          ，         it.w 
		if (cnt == n - 1)  //      n-1   ，         ，     
			break;
	}
	
	cout << ans;
	return 0;
}

primアルゴリズム
それに比べてkruskalアルゴリズムの実現はもっと簡単明瞭だと思いますが、primアルゴリズムには暗くて不安なところがあるような気がします.
しかし、この2つのアルゴリズムを比較するには、アルゴリズムの特徴から比較するのが合理的です.kruskalアルゴリズムは疎図に適しており,primアルゴリズムは稠密図に適している.テーマのデータ規模の展示から見ると、疎図が多いような気がします.

#include 
#include 
#include 
#include 
using namespace std;

//   ：
//1. PQ.empty() cnt    prim     ，                
//2.   prim        Edge   u   ，    u 
//3.   Edge        G   ，        in PQ        
//4.                    ，         ，            ，
//            

struct Edge{   //                        ，              
	int v, w;
	Edge() { }
	Edge(int _v, int _w): v(_v), w(_w) { }
	friend bool operator<(Edge a, Edge b){
		return a.w > b.w;  //  ，                  
	}
};

int n, m, root, ans;
const int MAXV = 50010;
const int MAXE = 100010;
vector<vector<Edge> > G(MAXV);
bool in[MAXV];

void prim(){   
	ans = 0;
	fill(in, in + MAXV, false);
	priority_queue<Edge> PQ;
	in[root] = true;
	for (auto it : G[root])
		if (!in[it.v])
			PQ.push(it);
	int cnt = 0;  //cnt                
	while (!PQ.empty()){  //          cnt   ，  cnt!=n，   PQ       ，       
		Edge e = PQ.top();
		PQ.pop();
		if (!in[e.v]){  // in[e.v]==false，  e      （         ） 
						//  PQ                ，          
			in[e.v] = true;
			cnt++;
			ans = max(ans, e.w);
			for (auto it : G[e.v])
				if (!in[it.v])
					PQ.push(it);
		}
		if (cnt == n - 1)  // cnt==n-1      
			break;
	}
}

int main(){
	cin >> n >> m >> root;
	int u, v, w;
	for (int i = 1; i <= m; i++){
		cin >> u >> v >> w;
		G[u].push_back(Edge(v, w));
		G[v].push_back(Edge(u, w));  //          
	}
	prim();
	cout << ans;
	return 0;
}

シングルソース最短パス
この問題を最初に使用したのはdijkstraアルゴリズムで、元のdijkstraアルゴリズムに基づいて少し変形する必要があります.ここではrootをソースとし、他のノードに到達する経路の長さは一般的な経路上の重みを加算するのではなく、経路上の重みが最も大きいエッジの重みを経路の長さとします.その正確性については、ここでは詳細な証明をせず、理解を助ける方法を提供する:経路r->u->vがあると仮定し、u->vの重みを経路r->u->v上の最大重みから経路r->u上の最大重みを減算し、前者は後者を含むため、この差は必ず負ではない.これは,経路上の最大重みを経路長とする問題が本質的に一般的な単一ソース最短経路問題であり,エッジ重みが負ではないことを意味する.
dijkstraアルゴリズム
この問題を解決するには、基本的なdijkstraアルゴリズムに基づいて、経路緩和を行うときに修正するだけです.

#include 
#include 
#include 
#include 
using namespace std;

//           dijkstra   

struct edge{
	int v;
	int weight;
	edge() { }
	edge(int _v, int _weight): v(_v), weight(_weight) {	}
};

struct node{
	int id;
	int dist;
	node() { }
	node(int _id, int _dist): id(_id), dist(_dist) { }
	friend bool operator<(node a, node b){  //  friend    
		return a.dist > b.dist;  //     ，                   
	}
};

int n, m, root;
const int MAXV = 500010;
const int INF = 0x3fffffff;
vector<vector<edge> > Adj(MAXV);
int d[MAXV];
bool vis[MAXV] = {false};

void dijkstra(){
	fill(d, d + MAXV, INF);
	d[root] = 0;
	priority_queue<node> PQ;
	for (int i = 1; i <= n; i++)
		PQ.push(node(i, d[i]));
		
	int u;
	for (int i = 1; i < n; i++){
		while (vis[u = PQ.top().id])
			PQ.pop();
		PQ.pop();
		vis[u] = true;
		if (d[u] == INF)
			return;
		edge it;
		for (int j = 0; j < Adj[u].size(); j++)
			if (!vis[(it = Adj[u][j]).v] && max(d[u], it.weight) < d[it.v]){  
				//    dijkstra        
				d[it.v] = max(d[u], it.weight);
				PQ.push(node(it.v, d[it.v]));
			}
	}
}

int main(){
	cin >> n >> m >> root;
	int u, v, w;
	for (int i = 1; i <= m; i++){
		cin >> u >> v >> w;
		Adj[u].push_back(edge(v, w));  
		Adj[v].push_back(edge(u, w));  //dijkstra       ，                 
	}
	dijkstra();
	int m = 0;
	for (int i = 1; i <= n; i++)
		m = max(m, d[i]);
	cout << m;
	return 0;
}

spfaアルゴリズム
次のプログラムは、上記のdijkstraアルゴリズムのプログラムとほぼ近いが、dijkstra関数がspfa関数に変換され、後者はinq配列が多く、vis配列が少なく、後者は優先順位キューを使用する必要がないため、構造体nodeを定義する必要はない.このように見ると、spfaはdijkstraよりも実現しやすく、効率もほとんど変わらない.

#include 
#include 
#include 
#include 
using namespace std;

//spfa  

struct edge{
	int v, w;
	edge() { }
	edge(int _v, int _w): v(_v), w(_w) { }
};

int n, m, root;
const int MAXV = 50010;
const int INF = 0x3fffffff;
vector<vector<edge> > Adj(MAXV);
int d[MAXV];
bool inq[MAXV];

void spfa(){
	fill(d, d + MAXV, INF);
	fill(inq, inq + MAXV, false);
	d[root] = 0;
	queue<int> Q;
	Q.push(root);
	inq[root] = true;
	int u;
	while (!Q.empty()){
		u = Q.front();  //   front  top 
		Q.pop();
		inq[u] = false;
		for (auto it : Adj[u]){
			if (max(d[u], it.w) < d[it.v]){
				d[it.v] = max(d[u], it.w);
				if (!inq[it.v]){
					inq[it.v] = true;
					Q.push(it.v);
				}
			}
		}
	}
}

int main(){
	cin >> n >> m >> root;
	int u, v, w;
	for (int i = 1; i <= m; i++){
		cin >> u >> v >> w;
		Adj[u].push_back(edge(v, w));  
		Adj[v].push_back(edge(u, w));  //             ，                 
	}
	spfa();
	int m = 0;
	for (int i = 1; i <= n; i++)
		m = max(m, d[i]);
	cout << m;
	return 0;
}