図論-ディジェストラアルゴリズムと最小生成ツリー

前言
ディジェストラアルゴリズムを復習します.最小生成ツリーのPrimアルゴリズムはディジェストラアルゴリズムと極めて似ているので、ついでに最小生成ツリーを復習し、ついでに2つの水問題を探してコードの正確性を検証します.
ディジェストラアルゴリズム
目的
このアルゴリズムは単一ソースの最短ルートに用いられて、1つの図の中で、起点Sから終点Eまでの最短経路を求めます
構想
アルゴリズムは貪欲な思想に基づいて、簡単に言えば2つのステップです.

起点距離他の点の最短距離の中で最も小さい

を探し出す

他の点の最短距離を最小で更新し、更新が完了すると

を捨てる.
私が見たように、ディジェストラはソートに似ていて、起点から他の点への経路がエッジであると仮定しています.

最短のエッジを選択し、最短のエッジで他のエッジを更新します.

は、さらに第2の短いエッジを介して、他のエッジを更新する.

全体のプロセスは、開始点から他の点までの最短エッジ

を小さいから大きい順に見つけることである.
タイトル
牛客網:https://ac.nowcoder.com/acm/problem/17511
一般的な方法
まず頂点を巡回し、その頂点を他の頂点のエッジに巡回します.時間の複雑さ:(O(n^2)).

#include 
#define ll long long
#define MAX 1005
using namespace std;
 
int mp[MAX][MAX],ans[MAX],n,m,s,t;
bool used[MAX];
 
void init(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    memset(mp,0x3f,sizeof(mp));
    memset(ans,0x3f,sizeof(ans));
    memset(used,false,sizeof(used));
    ans[s] = 0;
    for(int i = 1;i <= m;i++){
        int x,y,v;
        scanf("%d%d%d",&x,&y,&v);
        mp[x][y] = mp[y][x] = min(mp[y][x],v);
        if (x == s) ans[y] = mp[x][y];
        else if (y == s) ans[x] = mp[x][y];
    }
}
int dijkstra(int start,int end){
 
    while(true){
        int min_edge = 0;
        for(int i = 1;i <= n;i++)//                  
            if (!used[i]&&(!min_edge || ans[i] < ans[min_edge]))
                min_edge = i;
        //      ，     
        if (min_edge == end || !min_edge) break;
        used[min_edge] = true;
 
        for(int i = 1;i <= n;i++)
            ans[i] = min(ans[i],ans[min_edge]+mp[min_edge][i]);
    }
 
    return ans[end]==0x3f3f3f3f?-1:ans[end];
}
 
int main(){
    init();
    printf("%d
",dijkstra(s,t));
    return 0;
}

ゆうせんキュー
mは辺数、nは頂点数で結論を先に出し、時間複雑度(O(m*logn)).

for(int i = 1;i <= n;i++)//                  
    if (!used[i]&&(!min_edge || ans[i] < ans[min_edge]))
        min_edge = i;

明らかに、上記のコードでは、優先キュー(スタック)を使用して時間の複雑さを(O(logn))に下げることができますが!!!次はforループもあるので、自分の時間の複雑さは(O(n^2))です.

for(int i = 1;i <= n;i++)
    ans[i] = min(ans[i],ans[min_edge]+mp[min_edge][i]);

では、ここも直してもらえませんか.点から点までエッジがあるとは限らないため、すべての頂点を巡回する必要はありません.この場合、エッジを巡回するだけでいいです.つまり、エッジを格納し、隣接テーブルを使用します.
まとめてみると、プロセス全体の各頂点は複数回遍歴する可能性がありますが、そのうち1回だけ隣接するエッジを遍歴する必要があります.つまり、すべてのエッジも1回だけ遍歴する必要があります(無方向エッジは2回です).スタックが使用されているため、スタックを使用する時間の複雑さを加える必要があります.したがって、総時間の複雑さは(O(m*logn))です.
次はコードです

#include 
#define ll long long
#define MAX 1005
using namespace std;

int ans[MAX],n,m,s,t;//ans            
vector> mp[MAX*10];//      ，mp      ，pair        ，        
void init(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	memset(ans,0x3f,sizeof(ans));
	ans[s] = 0;
	for(int i = 1;i <= m;i++){
		int x,y,v;
		scanf("%d%d%d",&x,&y,&v);
		mp[x].push_back(make_pair(v,y));
		mp[y].push_back(make_pair(v,x));
	}
}
int dijkstra(int start,int end){

	priority_queue,vector>,greater> > p_que;
	p_que.push(make_pair(ans[start],start));//pair        ，        

	while(!p_que.empty()){
		pair node = p_que.top();
		p_que.pop();
		if (node.first > ans[node.second]) continue;
		for(int i = mp[node.second].size()-1;i >= 0;i--){
			pair temp = mp[node.second][i];
			if (ans[temp.second] > ans[node.second]+temp.first){
				ans[temp.second] = ans[node.second]+temp.first;
				p_que.push(make_pair(ans[temp.second],temp.second));
			}
		}
	}

	return ans[end]==0x3f3f3f3f?-1:ans[end];
}

int main(){
	init();
	printf("%d
",dijkstra(s,t));
	return 0;
}

最小生成ツリー
目的
無方向図を与える

生成ツリー:任意の2点が互いに通じるサブマップであり、ツリー

である.

最小生成ツリー:エッジに値があり、すべてのエッジと最小の生成ツリー

構想
ディジェストラアルゴリズムが1つの点を起点として、その起点から他のすべての点までの最小値を求めると仮定すると、最小生成ツリーのPrimアルゴリズムは、1つの集合(複数の点がある)を起点として、その集合から他のすべての点までの最小値を求め、和を求める.

ループごとに、集合と非集合の点の最小エッジを見つけ、この点が(x)

であると仮定する.

集合(x)点を加え、(x)と他の点のエッジを巡回し、エッジ(edge[x][y])<集合から(y)までの距離があると仮定すると、集合から(y)までの距離

が更新される

は、第1のステップ

に戻る
タイトル
牛客網:https://ac.nowcoder.com/acm/problem/15108
コード#コード#
明らかに,ディジェストラと同様にスタックを用いて最適化することができ,時間の問題のため,通常のコードのみが与えられる.

#include 
#define ll long long
#define MAX 1005
using namespace std;
 
int mp[MAX][MAX],ans[MAX],c,n,m;
bool used[MAX];

int Prim(int start){//              
 	int len = 0;
    while(true){
        int min_edge = 0;
        for(int i = 1;i <= n;i++)//                  
            if (!used[i]&&(!min_edge || ans[i] < ans[min_edge]))
                min_edge = i;
        //len >= 0x3f3f3f3f           ，     
        if (!min_edge || len >= 0x3f3f3f3f) break;
        used[min_edge] = true;
 		len += ans[min_edge];//     
        for(int i = 1;i <= n;i++)
            ans[i] = min(ans[i],mp[min_edge][i]);//            ，          
    }
 
    return len;
}
 
void init(int start){
	while(~scanf("%d%d%d",&c,&m,&n)){
	    memset(mp,0x3f,sizeof(mp));
	    memset(ans,0x3f,sizeof(ans));
	    memset(used,false,sizeof(used));
	    ans[start] = 0;
	    for(int i = 1;i <= m;i++){
	        int x,y,v;
	        scanf("%d%d%d",&x,&y,&v);
	        mp[x][y] = mp[y][x] = min(mp[y][x],v);
	    }
	    printf("%s
", Prim(1) <= c ?"Yes":"No");
	}
}
 
int main(){
    init(1);
    return 0;
}