2014年2014-10-24 12:29:00 UTC
最近在写一篇关于算法效率的文章,顺便学了一下Dijkstra的堆优化,我就给大家讲一下。
首先,代码上:
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <set>
#include <map>
#include <time.h>
using namespace std;
int n,dist[1000001],cn[1000001];
struct scmp
{
bool operator () (int a,int b)
{
if(dist[a]!=dist[b]) return dist[a]<dist[b]; else return a<b;
}
};
vector<int> vb[1000001],vv[1000001];
set<int,scmp> qs;
void dijkstra(int s)
{
for(int i=1;i<=n;i++) dist[i]=0x7ffffff;
dist[s]=0;
for(int i=1;i<=n;i++) qs.insert(i);
while(!qs.empty())
{
int u=*qs.begin();
qs.erase(u);
for(int i=0;i<cn[u];i++)
{
int v=vb[u][i],vx=vv[u][i];
if(dist[v]>dist[u]+vx)
{
qs.erase(v);
dist[v]=dist[u]+vx;
qs.insert(v);
}
}
}
}
int main()
{
int m,a,b,c;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
cn[a]++;
vb[a].push_back(b);
vv[a].push_back(c);
}
dijkstra(1);
for(int i=1;i<=n;i++) printf("%d ",dist[i]);
}
其实很简单,大家写Dijkstra是不是像这样:
Dijkstra核心思想:模拟一个集合,开始所有点的距离都设为到原点的距离,循环n次,每次从集合中找到一个距离最短的,从集合中移除,然后把未加入集合的点的距离更新为min(原距离,那个点到刚加入集合的点距离)。感觉和Prim算法思想差不多,它不能处理边权为负的情况。
然后呢,找到一个距离最短的这里用STL或者手写堆乱搞即可√,具体的看代码哈。
还有一点,大家说这个复杂度是O(nlogn)的。我开始以为,它只是把那个找到一个距离最短的那一部分搞成了log,别的没有变,貌似还是O(n^2)。
但是实际上,
- 每个节点顶多只会跑一遍Dijkstra。O(n)。(①跑一次我代码里的vis就变1了,以后就不会选它了,②在跑它之前,我代码里的那个set里只会有一个它,因为set忽略重复元素)
- 实际上像我这样搞类似边链表的东西,把一堆定点加到队列里,加在一起顶多跑n次,那平摊应该是O(1)。
- 堆里面复杂度顶多O(logn)。
然后O(n)*O(logn)=O(nlogn),差不多吧。
P.S: 最近会出一篇算法效率比较的文章,这篇只是前奏而已 ←_←
突然想起来好久没加Tag了,加两个Tag吧。
标签: 算法 Dijkstra
评论