Dijskstra算法

 

采用优先队列优化

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+;
const int maxm=1e6+;
int head[maxn],ver[maxm],edge[maxm],nxt[maxm],d[maxn];
int tot;
int v[maxn];
int n,m;
const int INF=0x3f3f3f3f;
priority_queue<pair<int,int> > q;
void add(int x,int y,int z)
{
ver[++tot]=y;
edge[tot]=z;
nxt[tot]=head[x];
head[x]=tot;
}
void dij()
{
memset(d,INF,sizeof(d));
memset(v,,sizeof(v));
d[]=;
q.push(make_pair(,));
while(q.size())
{
int x=q.top().second;
q.pop();
if(v[x]) continue;
v[x]=;
for(int i=head[x]; i; i=nxt[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 main()
{
int n,m;
while(scanf("%d%d",&n,&m)&&n)
{
tot=;
memset(head,,sizeof(head));
for(int i=; i<=m; i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dij();
printf("%d\n",d[n]);
}
}
//6 9
//1 2 1
//1 3 12
//2 3 9
//2 4 3
//3 5 5
//4 3 4
//4 5 13
//4 6 15
//5 6 4
//
//0 1 8 4 13 17
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int maxn = ;
const int INF = <<;
struct node
{
int x,d;
node() {}
node(int a,int b)
{
x=a;
d=b;
}
bool operator < (const node & a) const
{
if(d==a.d) return x<a.x; // 按d从小到大,x从大到小自动排序
else return d > a.d;
}
};
vector<node> eg[maxn];
int dis[maxn],n;
void Dijkstra(int s)
{
int i;
for(i=; i<=n; i++) dis[i]=INF;
dis[s]=;
//用优先队列优化,就是个堆
priority_queue<node> q;
q.push(node(s,dis[s]));
while(!q.empty())
{
node x=q.top();
q.pop();
for(i=; i<eg[x.x].size(); i++)
{
node y=eg[x.x][i];
if(dis[y.x]>x.d+y.d)
{
dis[y.x]=x.d+y.d;
q.push(node(y.x,dis[y.x]));
}
}
}
}
int main()
{
int a,b,d,m;
while(scanf("%d%d",&n,&m))
{
for(int i=; i<=n; i++) eg[i].clear();
while(m--)
{
scanf("%d%d%d",&a,&b,&d);
eg[a].push_back(node(b,d));
eg[b].push_back(node(a,d));
}
Dijkstra();
for(int i=; i<=n; i++)
printf("%d ", dis[i]);
}
return ;
}
//6 9
//1 2 1
//1 3 12
//2 3 9
//2 4 3
//3 5 5
//4 3 4
//4 5 13
//4 6 15
//5 6 4
//
//0 1 8 4 13 17

朴素版本,时间复杂度比上面的要高

#include<cstdio>
int e[][];
int dis[];
int book[];
int main()
{
int n, m;
int inf=;
scanf("%d%d", &n, &m);
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
if(i==j)
e[i][j]=;
else
e[i][j]=inf;
int t1, t2, t3;
for(int i=; i<=m; i++)
{
scanf("%d%d%d", &t1, &t2, &t3);
e[t1][t2]=t3;
}
for(int i=; i<=n; i++)
{
dis[i]=e[][i];
}
int u, min;
book[]=;
for(int i=; i<=n; i++)
{
min=inf;
for(int j=; j<=n; j++)
{
if(dis[j]<min && book[j]==)
{
u=j;
min=dis[j];
}
}
book[u]=;
for(int v=; v<=n; v++)
{
if(e[u][v]<inf && dis[v]>dis[u]+e[u][v])
{
dis[v]=dis[u]+e[u][v];
}
}
}
for(int i=; i<=n; i++)
printf("%d ", dis[i]);
}
上一篇:mysql数据库MHA高可用


下一篇:MySQL数据库实现高可用架构之MHA