Dijkstra狄克斯特拉

斯特拉"/>

Dijkstra狄克斯特拉

教学视频

狄克斯特拉算法

与prim普里姆算法的不同之处

prim与dijkstra算法都是基于"蓝白点私思想" ,所谓蓝白点思想就是开局所有点皆为蓝点,之后逐个加入,每次选出白点,直到所有蓝点消失,prim与dijkstra算法实现都有一个d数组,但是d数组的含义却不相同,prim是集合V中到集合G-V中,两点之间的最小值,而dj是从源点出发,到该点的最小值,两种算法的d数组含义截然不同,但是实现逻辑都是基于蓝白点思想,先找出d数组中为最小值的结点u,在遍历与u相邻结点进行更新d数组中的值,区别在于如何更新prim是 m[u][v]<d[v]就更新,而dj是d[u]+m[u][v]<d[j]就更新!

注意:dijkstra算法不能用于权值为负的情况。会环化!

prime和dijkstra算法都是O(V^2),在没有优先队列优化的情况下。

代码实现:

#include <bits/stdc++.h>#define ll long long
using namespace std;const int maxn=1000+10;
int n,ans,ecnt,m;
int head[maxn],vis[maxn];
int d[maxn],ma[maxn][maxn];
int p[maxn];
struct node
{int u,v,next;
} E[maxn];void add(int u,int v)
{E[++ecnt].u=u;E[ecnt].v=v;E[ecnt].next=head[u];head[u]=ecnt;
}void prim()
{int u;memset(d,0x7f7f7f7f,sizeof(d));d[1]=0;for(int i=1;i<=n;i++){u=0;for(int j=1;j<=n;j++){if(!vis[j]&&d[j]<d[u]) u=j;}vis[u]=1;cout<<u<<endl;ans+=d[u];//记录最小生成树的权值和for(int j=1;j<=n;j++){if(!vis[j]&&d[j]>ma[u][j]&&ma[u][j]!=-1)d[j]=ma[u][j];//更新两点距离最小的d}}
}void dijkstra()
{memset(d,0x7f7f7f7f,sizeof(d));d[0]=0;int u;for(int i=1;i<=n;i++){   u=n+1; //u初始为无穷大的点for(int j=0;j<n;j++){if(!vis[j]&&d[j]<d[u]) u=j;}vis[u]=1;for(int j=0;j<n;j++){if(!vis[j]&&d[u]+ma[u][j]<d[j]){d[j]=d[u]+ma[u][j];//区别所在p[j]=u;}}}
}
int main()
{cin>>n;int u,v,k;memset(ma,0x7f7f7f7f,sizeof(ma));for(int i=1; i<=n; i++){cin>>u>>k;for(int j=1; j<=k; j++){cin>>v>>ma[u][v];}}dijkstra();for(int i=0;i<n;i++){cout<<i<<" "<<d[i]<<endl;}return 0;
}

优先队列优化Dijkstra算法

普通版的需要每次通过for循环找出最短路径,而有了优先队列,不必通过for循环可以直接拿出最短的路径。

#include <bits/stdc++.h>
using namespace std;
const int inf=0x7f7f7f7f;
const int maxn=10010;
int d[maxn],vis[maxn];//d存放最短路径长度,vis表示是否标记
int n,k,u;vector<pair<int,int> > M[maxn];//采用邻接表
typedef pair<int,int> pa;//定义pair类型的数据类型
priority_queue<pa,vector<pa>,greater<pa> > q;//使用优先队列,使用最小堆形成的优先队列void dijkstra()
{   //初始化memset(vis,0,sizeof(vis));memset(d,inf,sizeof(d));d[0]=0;q.push(make_pair(0,0));//将起始结点压入队列qwhile(!q.empty()){pair<int,int> t=q.top();//每次拿出最短路径q.pop();int u=t.second;//拿出uvis[u]=1;if(d[u]<t.first) continue;//别的点到t点的距离更短更新最开始到t点的距离,并且比最开始到u的路径短,所以这pair一定不是最短路径直接continuefor(int j=0;j<M[u].size();j++){int v=M[u][j].second;//取出到达点vif(d[v]>d[u]+M[u][j].first){d[v]=d[u]+M[u][j].first;//更新d[v]q.push(make_pair(d[v],v));//将新的路径压入队列}}}for(int i=0;i<n;i++){printf("%d %d\n",i,d[i]==inf?-1:d[i]);}
}int main()
{scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d",&u,&k);for(int j=0;j<k;j++){int v,c;scanf("%d%d",&v,&c);M[u].push_back(make_pair(c,v));//第一个int 存放权值,第二个存放结点编号}}dijkstra();return 0;
}

结构体版本:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef pair<int,int> pr;
int n,m;
vector <pr> M[maxn];//存图
int d[maxn],vis[maxn];
struct node //存放结点信息
{int id,d;node() {}node(int id,int d):id(id),d(d) {}inline bool operator<(const node b) const{return d>b.d;}
};void dijkstra(int st)
{memset(vis,0,sizeof(vis));memset(d,0x7f7f7f7f,sizeof(d));priority_queue<node> q;d[st]=0;q.push(node(st,0));node t;while(!q.empty()){t=q.top();q.pop();if(vis[t.id])continue;//与if(d[u]<t.first) 代码含义相同,存放node的id相同但是d[id]值不同,我们已经更新了最小的d[id]所以不用在遍历vis[t.id]=1;//标记for(int i=0; i<M[t.id].size(); i++){int j=M[t.id][i].first;if(d[j]>d[t.id]+M[t.id][i].second){d[j]=d[t.id]+M[t.id][i].second;q.push(node(j,d[j]));}}}
}int main()
{scanf("%d%d",&n,&m);for(int i=1; i<=m; i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);M[u].push_back(make_pair(v,w));}dijkstra(1);for(int i=1;i<=n;i++){printf("%d\n",d[i]);}return 0;
}

复杂度分析:
普通版本:O(V^2)

每次要选出d值最小的顶点,一共V次操作,并且每个点要搜索与v相邻的的顶点,所以每个点要V次操作,一共V个点所以为O(V^2)

优先队列版本:O((V+E)logV)

每次从优先队列中取出路径最小的pair需要VlogV,每次更新路径需要遍历与该点相邻的点设有E个,在添加入堆的复杂度为logv总共需要Elogv的复杂度,所以一共需要VlogV+ElogV=(V+E)logV的复杂度。

例题
爱与愁商店最短路径

#include <bits/stdc++.h>using namespace std;
const int maxn=210;
struct node
{int id;double v;node() {}node(int id,double v):id(id),v(v) {}bool operator<(const node b)const{return v>b.v;}
};
struct point
{int x,y;
} E[maxn];
vector<node>M[maxn];
double  d[maxn];
int vis[maxn];
int n,m,x,y,u,v;
double  dis(point a,point b)
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}void dijkstra(int start)
{fill(d+1,d+1+n,0x7f7f7f7f);memset(vis,0,sizeof(vis));priority_queue<node> q;q.push(node(start,0));//自己到自己的距离为0d[start]=0;node t;while(!q.empty()){t=q.top();q.pop();if(vis[t.id])continue;vis[t.id]=1;for(int i=0; i<M[t.id].size(); i++){int u=t.id;int v=M[t.id][i].id;double w=M[t.id][i].v;if(d[v]>d[u]+w){d[v]=d[u]+w;q.push(node(v,d[v]));}}}
}int main()
{scanf("%d",&n);for(int i=1; i<=n; i++){scanf("%d%d",&x,&y);E[i].x=x;E[i].y=y;}scanf("%d",&m);for(int i=1; i<=m; i++){scanf("%d%d",&u,&v);double k=dis(E[u],E[v]);M[u].push_back(node(v,k));M[v].push_back(node(u,k));}scanf("%d%d",&u,&v);dijkstra(u);printf("%.2f\n",d[v]);return 0;
}

链式前向星实现存图

#include <bits/stdc++.h>#define ll long long
#define pr pair<double,int>
using namespace std;const int maxn=2000+10;
int n,ans,ecnt,m;double d[maxn],vis[maxn];
int X[maxn],Y[maxn];
int head[maxn];struct node
{int u,v,next;double w;
} E[maxn];void add(int u,int v,double w)
{E[++ecnt].u=u;E[ecnt].v=v;E[ecnt].w=w;E[ecnt].next=head[u];head[u]=ecnt;
}priority_queue<pr,vector<pr>,greater<pr> > q;//注意最小堆是greater,默认以pair中first排序double dis(int a,int b)
{return sqrt((X[a]-X[b])*(X[a]-X[b])+(Y[a]-Y[b])*(Y[a]-Y[b]));
}void dijkstra(int u)
{memset(d,0x7f7f7f7f,sizeof(d));d[u]=0;q.push(make_pair(0,u));while(!q.empty()){int x=q.top().second;q.pop();if(vis[x])continue;vis[x]=1;for(int i=head[x];i; i=E[i].next){int j=E[i].v;if(!vis[j]&&d[j]>E[i].w+d[x]){d[j]=d[x]+E[i].w;//   cout<<"u"<<x<<"V"<<j<<"s"<<d[j]<<endl;q.push(make_pair(d[j],j));}}}
}int main()
{cin>>n;for(int i=1; i<=n; i++){cin>>X[i]>>Y[i];}cin>>m;int x,y;for(int i=1; i<=m; i++){cin>>x>>y;add(x,y,dis(x,y));add(y,x,dis(x,y));}cin>>x>>y;dijkstra(x);printf("%.2lf",d[y]);return 0;
}