模板题---2.1（图论)-创新互联

最短路径

1. Dijkstra
2.Dijkstra优化
3.bellman_ford()算法
4.spfa算法
- (1)不含负环
- (2)含负环

创新互联专注于企业成都营销网站建设、网站重做改版、乌拉特中网站定制设计、自适应品牌网站建设、H5高端网站建设、商城网站定制开发、集团公司官网建设、成都外贸网站建设公司、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为乌拉特中等各大城市提供网站开发制作服务。1. Dijkstra

题目：dijkstra求最短路径

#include#include
#includeusing namespace std;
const int N=510,INF=0x3f3f3f3f;

int g[N][N];
int dist[N];
int st[N];
int n,m;

int dijkstra()
{memset(dist,INF,sizeof dist);
	dist[1]=0;
	for(int i=0;i		int t=-1;
		for(int j=1;j<=n;j++)
		{	if(st[j]==0&&(t==-1||dist[t]>dist[j]))
				t=j;
		}
		st[t]=1;
		for(int j=1;j<=n;j++)
		{	if(st[j]==0)
				dist[j]=min(dist[j],dist[t]+g[t][j]);
		}
	}
	if(dist[n]==0x3f3f3f3f)
		return -1;
	else
		return dist[n];
}
int main()
{cin>>n>>m;
	memset(g,INF,sizeof g);
	for(int i=0;iint x,y,z;
		cin>>x>>y>>z;
		g[x][y]=min(g[x][y],z);
	}
	cout<

2.Dijkstra优化在记录优化之前，先要知道使用一个类模板—优先队列(stl):
STL中定义优先队列的模板类为priority_queue，其定义如下：
templateclass priority_queue;
模板里面有三个参数，第一个为元素的类型，第二个为所使用的容器（vector或deque），第三个为一个比较的规则，决定是大优先队列还是最小优先队列，默认的less为大优先队列，实现方式是大堆，greater为最小优先队列，实现方式是最小堆，结构都是二叉树。
大根堆就是根节点大，小根堆就是根节点最小。
#include//c++标准头文件，可以使用cout,cin等标准库函数 
#include//使用priority_queue时需要的头文件 
using namespace std;//命名空间，防止重名给程序带来各种隐患，使用cin,cout,stack,map,set,vector,queue时都要使用
struct test {//定义一个结构体test 
	int val;
	test(int v) {//构造函数 
		this->val = v;
	}
	bool operator >(const test t)const {//重载运算符>if (val >t.val)
			return true;
		else
			return false;
	}
	bool operator< (const test t)const {//重载运算符
		return val< t.val;
	}
};
int main() {priority_queue, less>q1;//定义一个大顶堆q1 
	cout<< "定义一个大根堆q1: priority_queue,less>q1"<< endl;
	q1.push(test(10));//向队列中添加一个test，val的值为10 
	q1.push(test(5));//向队列中添加一个test，val的值为5
	q1.push(test(7));//向队列中添加一个test，val的值为7
	cout<< "按顺序添加val的值为10、5、7的test,目前队列的元素：test(10) test(5) test(7)"<< endl;
	cout<< "q1.top().val="<< q1.top().val<< endl;
	cout<< endl;


	q1.pop();
	cout<< "q1.pop()后，目前队列的元素：test(5) test(7)"<< endl;
	cout<< "q1.top().val="<< q1.top().val<< endl;
	cout<< endl;


	q1.pop();
	cout<< "q1.pop()后，目前队列的元素：test(5)"<< endl;
	cout<< "q1.top().val="<< q1.top().val<< endl;
	cout<< endl;

	q1.pop();
	cout<< "q1.pop()后，目前队列是空的"<< endl;
	cout<< "目前队列是空的，不能使用q1.top()查询队首元素"<< endl;
	cout<< endl<< endl;



	priority_queue, greater>q2;//定义一个大顶堆q1 
	cout<< "定义一个小根堆q2: priority_queue,greate>q2"<< endl;
	q2.push(test(10));//向队列中添加一个test，val的值为10 
	q2.push(test(5));//向队列中添加一个test，val的值为5
	q2.push(test(7));//向队列中添加一个test，val的值为7
	cout<< "按顺序添加val的值为10、5、7的test,目前队列的元素：test(10) test(5) test(7)"<< endl;
	cout<< "q2.top().val="<< q2.top().val<< endl;
	cout<< endl;


	q2.pop();
	cout<< "q2.pop()后，目前队列的元素：test(10) test(7)"<< endl;
	cout<< "q2.top().val="<< q2.top().val<< endl;
	cout<< endl;


	q2.pop();
	cout<< "q2.pop()后，目前队列的元素：test(10)"<< endl;
	cout<< "q2.top().val="<< q2.top().val<< endl;
	cout<< endl;

	q2.pop();
	cout<< "q1.pop()后，目前队列是空的"<< endl;
	cout<< "目前队列是空的，不能使用q2.top()查询队首元素"<< endl;


}
题目：dijkstra优化
#include#include#include#includeusing namespace std;
const int N=150010,M=N*2,INF=0x3f3f3f3f;
typedef pairPII;
int head[N],e[N],ne[N],w[N];
int dist[N],st[N];
int idx,n,m;

void add(int a,int b,int c)
{e[idx]=b;
	w[idx]=c;
	ne[idx]=head[a];
	head[a]=idx++;
}

int dijkstra()
{memset(dist,INF,sizeof dist);
	dist[1]=0;
	priority_queue,greater>heap;
	heap.push({0,1});
	while(heap.size())
	{PII k=heap.top();
		heap.pop();
		int distance=k.first,ver=k.second;
		if(st[ver]==1)continue;
		else st[ver]=1;
		for(int i=head[ver];i!=-1;i=ne[i])
		{	int j=e[i];
			if(st[j]==0&&dist[j]>distance+w[i])
			{		dist[j]=distance+w[i];
				heap.push({dist[j],j});
			}
		}
	}
	if(dist[n]==INF)return -1;
	else return dist[n];
}
int main()
{cin>>n>>m;
	memset(head,-1,sizeof head);
	for(int i=0;iint a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	cout<
3.bellman_ford()算法核心：对所有的点进行“对邻接边尝试松弛”即dist[to]=min(dist[to],dist[from]+w[from][to]);
题目；bellmanford
#include#include#include
using namespace std;
const int N=100010;
struct edge
{int a,b,w;
}edge[N];
int dist[N];
int backup[N];
int n,m,k;

int bellman_ford()
{memset(dist,0x3f3f3f3f,sizeof dist);
	dist[1]=0;
	for(int i=1;i<=k;i++)
	{memcpy(backup,dist,sizeof dist);
		for(int j=1;j<=m;j++)
		{	int a=edge[j].a,b=edge[j].b,w=edge[j].w;
			dist[b]=min(dist[b],backup[a]+w);
		}
	}
	return dist[n];
}


int main()
{cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{int a,b,c;
		cin>>a>>b>>c;
		edge[i].a=a,edge[i].b=b,edge[i].w=c;
	}
	
	int t=bellman_ford();
	if(t>=0x3f3f3f3f/2)cout<<"impossible";
	else cout<
4.spfa算法spfa算法就是bellman_ford算法的优化版本
Bellman_ford算法会遍历所有的边，但是有很多的边遍历了其实没有什么意义，我们只用遍历那些到源点距离变小的点所连接的边即可，只有当一个点的前驱结点更新了，该节点才会得到更新；因此考虑到这一点，我们将创建一个队列每一次加入距离被更新的结点。
(1)不含负环题目：spfa
#include#include#include
#includeusing namespace std;
const int N=1e5+10;
int head[N],e[N],ne[N],w[N],idx;
int dist[N],st[N];
int n,m;

void add(int a,int b,int c)
{e[idx]=b,ne[idx]=head[a],w[idx]=c,head[a]=idx++;
}

void spaf()
{queueq;
	q.push(1);
	dist[1]=0;
	st[1]=1;
	while(!q.empty())
	{		int t=q.front();
		q.pop();
		st[t]=0;
		for(int i=head[t];i!=-1;i=ne[i])
		{	int a=e[i],b=w[i];
			if(dist[a]>dist[t]+b)
			{		dist[a]=dist[t]+b;
				if(st[a]==0)
				{st[a]=1;
					q.push(a);
				}
			}
		}
	}	
}

int main()
{cin>>n>>m;
	memset(head,-1,sizeof head);
	memset(dist,0x3f,sizeof dist);
	for(int i=0;iint a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	spaf();
	if(dist[n]==0x3f3f3f3f)
		cout<<"impossible";
	else
		cout<
(2)含负环题目：spaf判断负环
#include#include#include
#includeusing namespace std;
const int N=1e4+10;

int head[N],e[N],ne[N],w[N],idx;
int st[N],cnt[N],dist[N];
int n,m;

void add(int a,int b,int c)
{e[idx]=b,ne[idx]=head[a],w[idx]=c,head[a]=idx++;
}

bool spaf()
{queueq;
	for(int i=1;i<=n;i++)
	{q.push(i);
		st[i]=1;
	}
	dist[1]=0;
	while(!q.empty())
	{int t=q.front();
		q.pop();
		st[t]=0;
		for(int i=head[t];i!=-1;i=ne[i])
		{	int j=e[i],k=w[i];
			if(dist[j]>dist[t]+k)
			{		dist[j]=dist[t]+k;
				cnt[j]++;
				if(cnt[j]>m)
					return true;
				if(st[j]==0)
				{st[j]=1;
					q.push(j);
				}
			}
		}
	}
	return false;
}

int main()
{cin>>n>>m;
	memset(head,-1,sizeof head);
	memset(dist,0x3f,sizeof dist);
	for(int i=0;iint a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	if(spaf())
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
}
                
     你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
                

                文章名称：模板题---2.1（图论)-创新互联                

                网页链接：http://pwwzsj.com/article/ccsshs.html


        
            其他资讯
            
                
                        抖音代运营项目代理分站
                    

                        短视频代运营策划机构怎么样
                    

                        合伙抖音代运营合法吗安全吗
                    

                        企业网站设计哪里专业
                    

                        上蔡附近短视频代运营托管