欢迎来到天天文库
浏览记录
ID:49482703
大小:98.72 KB
页数:9页
时间:2020-02-25
《北京大学ACM暑期课讲义-Dijkstra Algorithm.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、Dijkstra'sAlgorithm解决无负权边的带权有向图或无向图的单源最短路问题贪心思想,若离s前k-1近的点已经被确定,构成点集P,那么从s到离s第k近的点t的最短路径,{s,p1,p2…pi,t}满足s,p1,p2…pi∈P。否则假设pi∉P,则因为边权非负,pi到t的路径≥0,则d[pi]≤d[t],pi才是第k近d[i]=min(d[pi]+cost(pi,i)),i∉P,pi∈Pd[t]=min(d[i]),i∉PDijkstra'sAlgorithm初始令d[s]=0,d[i]=+∞,P=∅找到点i
2、∉P,且d[i]最小把i添入P,对于任意j∉P,若d[i]+cost(i,j)3、]=2但用Dijkstra算法求得d[1,2]=3POJ3159Candies有N个孩子(N<=3000)分糖果。有M个关系(M<=150000)。每个关系形如:ABC表示第B个学生比第A个学生多分到的糖果数目,不能超过C求第N个学生最多比第1个学生能多分几个糖果POJ3159Candies有N个孩子(N<=3000)分糖果。有M个关系(M<=150000)。每个关系形如:ABC表示第B个学生比第A个学生多分到的糖果数目,不能超过C求第N个学生最多比第1个学生能多分几个糖果思路:30000点,150000边的稀疏图求4、单源最短路读入“ABC”,就添加A->B的有向边,权值为C然后求1到N的最短路用prioirty_queue实现dijkstra+堆的POJ3159Candies//byguowei#include#include#include#include#includeusingnamespacestd;structCNode{intk;//端点intw;//权值,或k到已经求出最短路的那些点的最短距离};booloperator<(cons5、tCNode&d1,constCNode&d2){returnd1.w>d2.w;//priority_queue总是将最大的元素出列}intaDist[30010];priority_queuepq;boolbUsed[30010]={0};//vectorv[30010];error,如果用这个,则在poj会超时。说明vector对象的初始化,也是需要可观时间的vector>v;constunsignedintINFINITE=100000000;intma6、in(){intN,M,a,b,c;inti,j,k;CNodep,q;scanf("%d%d",&N,&M);v.clear();v.resize(N+1);memset(bUsed,0,sizeof(bUsed));for(i=1;i<=M;i++){scanf("%d%d%d",&a,&b,&c);p.k=b;p.w=c;v[a].push_back(p);}p.k=1;p.w=0;pq.push(p);while(!pq.empty()){p=pq.top();pq.pop();if(bUsed[p.k])/7、/已经求出了最短路continue;bUsed[p.k]=true;if(p.k==N)break;for(i=0,j=v[p.k].size();i
3、]=2但用Dijkstra算法求得d[1,2]=3POJ3159Candies有N个孩子(N<=3000)分糖果。有M个关系(M<=150000)。每个关系形如:ABC表示第B个学生比第A个学生多分到的糖果数目,不能超过C求第N个学生最多比第1个学生能多分几个糖果POJ3159Candies有N个孩子(N<=3000)分糖果。有M个关系(M<=150000)。每个关系形如:ABC表示第B个学生比第A个学生多分到的糖果数目,不能超过C求第N个学生最多比第1个学生能多分几个糖果思路:30000点,150000边的稀疏图求
4、单源最短路读入“ABC”,就添加A->B的有向边,权值为C然后求1到N的最短路用prioirty_queue实现dijkstra+堆的POJ3159Candies//byguowei#include#include#include#include#includeusingnamespacestd;structCNode{intk;//端点intw;//权值,或k到已经求出最短路的那些点的最短距离};booloperator<(cons
5、tCNode&d1,constCNode&d2){returnd1.w>d2.w;//priority_queue总是将最大的元素出列}intaDist[30010];priority_queuepq;boolbUsed[30010]={0};//vectorv[30010];error,如果用这个,则在poj会超时。说明vector对象的初始化,也是需要可观时间的vector>v;constunsignedintINFINITE=100000000;intma
6、in(){intN,M,a,b,c;inti,j,k;CNodep,q;scanf("%d%d",&N,&M);v.clear();v.resize(N+1);memset(bUsed,0,sizeof(bUsed));for(i=1;i<=M;i++){scanf("%d%d%d",&a,&b,&c);p.k=b;p.w=c;v[a].push_back(p);}p.k=1;p.w=0;pq.push(p);while(!pq.empty()){p=pq.top();pq.pop();if(bUsed[p.k])/
7、/已经求出了最短路continue;bUsed[p.k]=true;if(p.k==N)break;for(i=0,j=v[p.k].size();i
此文档下载收益归作者所有