Dijkstra算法:一个顶点到其余各顶点的最短路径算法。
伪代码:
vis[i]=0;
d[i]=图中边s-i的权值;无s-i边则d[i]=MAX;d[s]=0;
标记s;
循环n-1次{
找出未被标记中最小的d[x];
标记x点;
更新d[i],d[i]=min(d[i],d[x]+图中x-i边长度);
}
代码:
void Dijkstra(int s){
for(int i=1;i<=n;i++) d[i]=inf;//初始化
for(int i=1;i<=n;i++)//将图中与s的边的权值赋给d[i] ,d[i]表示s->i这条边的距离
d[i]=g[s][i];
d[s]=0;
vis[s]=1;//标记
for(int i=1;i<=n-1;i++){
long long min1=inf;
int p=0;
for(int j=1;j<=n;j++)
if(!vis[j]&&min1>d[j]){ min1=d[j]; p=j;}//在所有未标记点中找到d值最小的节点p
if(p==0) break;
vis[p]=1;
for(int j=1;j<=n;j++){//更新,s->j之间的最短距离 d[j]=min(d[p]+p->j,d[j])
if(d[p]+g[p][j]<d[j]){
d[j]=d[p]+g[p][j];
}
}
}
}
优先队列优化的Dijkstra:
优先队列:普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出的行为特征。通常采用堆数据结构来实现。优先队列默认为大根堆。priority_queue< int,vector<int >,greater<int > > q定义q为小根堆。
struct Edge{
int from , to ,dist;//起点、终点、边长
Edge(int u,int v,int d):from(u),to(v),dist(d) {}
};
vector<Edge> edge;
vector<int> g[maxn];//g[i]储存的是点i相连的边在edge中的位置
int d[maxn];//d[i] s->i的距离
int vis[maxn]={0};//标记
struct node
{
int u,d;//
bool operator < (const node& x) const{
return d>x.d ;//定义小于号(小于号定义为大于号)
}
};//优先队列元素类型
void Dijkstra(int s){
priority_queue< node > q;
for(int i=1;i<=n;i++) d[i]=inf;//初始化
d[s]=0;
q.push((node){s,0});//进队列终点s 路径长为0
while( !q.empty() ){
node x=q.top(); q.pop();//取顶(优先队列内d最小)
int u=x.u;
if(vis[u]) continue;//队列为空 即为所有点都更新了
vis[u] =1;//标记
for(int i=0;i<g[u].size();i++){//搜索u所有连边
Edge e=edge[g[u][i]];//连边
if(d[e.to]>d[u]+e.dist){
d[e.to]=d[u]+e.dist;//松弛操作
q.push((node){ e.to,d[e.to]});//把新遍历到的点加入队列中
}
}
}
}