北京大学ACM暑期课讲义-Dijkstra Algorithm.ppt

《北京大学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<(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