0%

dijkstra

dijkstra

一种单源最短路算法,是一种贪心算法,yj一般使用堆优化

不用堆优化是$O(n^2)$,堆优化后是$O((m+n)logn)$


流程 :

  • 初始化d[1]=0;其余节点为INF;
  • 寻找没有标记过的,距离最小的节点x,标记之
    • 使用x,遍历没有标记过的所有点,看是否能用它为中继,获得更小的dist值
    • 重复上两步,直到每个点都被标记

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
const int N=100010,M=1000010;
int head[N],ver[M],edge[M],Next[M],d[N];
bool v[N];
int n,m,tot;
//大顶堆,pair.sec是节点编号
//pair.fir是dist的相反数,用于转小顶
priority_queue<pair<int ,int> >q;
void add(int x,int y,int z){
ver[++tot]=y,edge[tot]=z;
Next[tot]=head[x],head[x]=tot;
//区别在于add
}

void dij(){
memset(d,0x3f,sizeof d);
memset(v,0,sizeof v);
d[1]=0;
q.push(make_pair(0,1));
while(q.size()){
int x=q.top().second;q.pop();
if(v[x])continue;
v[x]=1;
for(int i=head[x];i;i=Next[i]){
int y=ver[i];
int z=edge[i];
if(d[y]>d[x]+z){
d[y]=d[x]+z;
q.push(
make_pair(-d[y],y)
//存进去只是排序 而已
);
}
}
}
}

int mian(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
//
dij();
for(int i=1;i<=m;i++){
cout<<d[i]<<endl;
}
}