重庆分公司
重庆分公司，新征程启航
为企业提供网站建设、域名注册、服务器等服务
模板题---2.1（图论)-创新互联
最短路径
文章名称：模板题---2.1（图论)-创新互联
文章出自：http://cqcxhl.cn/article/ccsshs.html
- 1. Dijkstra
- 2.Dijkstra优化
- 3.bellman_ford()算法
- 4.spfa算法
- (1)不含负环
- (2)含负环
题目：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< 在记录优化之前，先要知道使用一个类模板—优先队列(stl):
STL中定义优先队列的模板类为priority_queue，其定义如下：
template
模板里面有三个参数，第一个为元素的类型，第二个为所使用的容器（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< 核心：对所有的点进行“对邻接边尝试松弛”即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< spfa算法就是bellman_ford算法的优化版本
Bellman_ford算法会遍历所有的边，但是有很多的边遍历了其实没有什么意义，我们只用遍历那些到源点距离变小的点所连接的边即可，只有当一个点的前驱结点更新了，该节点才会得到更新；因此考虑到这一点，我们将创建一个队列每一次加入距离被更新的结点。
题目：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< 题目：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://cqcxhl.cn/article/ccsshs.html