Dijkstra 算法小结
By Wine93 2013.11
1. Dijkstra 算法相关介绍
算法阐述：Dijkstra是解决单源最短路径的算法,它可以在O(n^2)内计算出源点(s)到图中任何顶点的最短路,但是该算法不能处理存在负权边的图(证明中会给出)。
Dijkstra一般有2种实现，一种采用邻接矩阵，复杂度为O(n^2)，这种实现适用于稠密图 (边多点少)，还有一种是采用临接表+heap(可用优先队列代替)实现，实现的复杂度为( m*log(n) ) (m为边数,n为顶点数)，该实现适用于稀疏图(边少点多)，各有各的优缺，视实际情况选择.
算法简单证明:Dijkstra有2张表(OPEN,CLOSE),我们可以认为一个表存储已经已经计算出最短路径的顶点(假设U)，而另一个则存储没有计算出最短路径的顶点(假设V)。Dijkstra每次都取出具有最短路径的顶点(假设NOW),视其就是该顶点的最短路.因为在当前U表中全部扩展的顶点中，NOW顶点是路径最短的顶点，也就是说，其他当前全部可以到达的顶点中,只有大于或等于NOW顶点，如果 通过这些顶点再到达NOW顶点,势必会比现在NOW顶点的路径长，因为原来就大于等于NOW顶点了, 所以NOW顶点路径长度就是源点到该顶点的最短路径.但是如果存在负权边，则会出现通过其他顶点到达NOW顶点的路径长度小于当前NOW顶点的路径长度，这就是为什么Dijkstra不能处理负权边了(请读者看下面例图,模拟下Dijkstra的执行过程)
2.Dijkstra的相关应用举例
一.基础题
POJ 1511 Invitation Cards
# include<cstdio> # include<cstring> # include<algorithm> # include<queue> # include<map> # include<vector> # include<utility> using namespace std; # define LL long long const LL inf=1LL<<62; const int maxn=1000005; const int maxm=1000005; typedef pair<int,LL> node; struct edge { int u,v,next; LL w; } e[maxm]; struct cmp { bool operator()(const node &a,const node &b)const { return a.second>b.second; } }; int num,head[maxn]; LL dis[maxn]; int n,m; bool vis[maxn]; priority_queue<node,vector<node>,cmp> q; inline void addedge(int u,int v,LL w) { e[num].u=u; e[num].v=v; e[num].w=w; e[num].next=head[u]; head[u]=num++; } void dijkstra(int s) { int i,u,v; for(int i=0;i<=n;i++) { dis[i]=inf; vis[i]=0; } dis[s]=0; q.push(make_pair(s,dis[s])); while(!q.empty()) { u=q.top().first; q.pop(); if(vis[u]) continue; vis[u]=1; for(i=head[u];i!=-1;i=e[i].next) { v=e[i].v; if(!vis[v]&&dis[u]+e[i].w<dis[v]) { dis[v]=dis[u]+e[i].w; q.push(make_pair(v,dis[v])); } } } } void init() { num=0; memset(head,-1,sizeof(head)); } int main() { //freopen("in.txt","r",stdin); vector<edge> vec; int T,u,v,i; LL w; LL ans; scanf("%d",&T); while(T--) { ans=0; vec.clear(); init(); scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d%I64d",&u,&v,&w); addedge(u,v,w); } dijkstra(1); for(i=1;i<=n;i++) ans+=dis[i]; for(i=0;i<num;i++) vec.push_back(e[i]); init(); for(i=0;i<vec.size();i++) addedge(vec[i].v,vec[i].u,vec[i].w); dijkstra(1); for(i=1;i<=n;i++) ans+=dis[i]; printf("%I64d\n",ans); } return 0; }
POJ 3013 Big Christmas Tre(重点在于思维的转换)
# include<cstdio> # include<cstring> # include<map> # include<vector> # include<queue> # include<algorithm> using namespace std; # define LL long long typedef pair<LL,int> PII; # define INF 1LL<<62 # define N 50005 # define M 100005 int num,head[N]; int vis[N]; LL dis[N]; priority_queue< PII,vector<PII>,greater<PII> >q; struct edge { int u,v,next; LL w; }e[M]; void addedge(int u,int v,LL w) { e[num].u=u; e[num].v=v; e[num].w=w; e[num].next=head[u]; head[u]=num++; } void dijkstra(int n,int s) { int i,u,v; for(i=0;i<=n;i++) { dis[i]=INF; vis[i]=0; } while(!q.empty()) q.pop(); dis[s]=0; q.push(PII(dis[s],s)); while(!q.empty()) { u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=1; for(i=head[u];i!=-1;i=e[i].next) { v=e[i].v; if(!vis[v]&&dis[u]+e[i].w<dis[v]) { dis[v]=dis[u]+e[i].w; q.push(PII(dis[v],v)); } } } } void init() { num=0; memset(head,-1,sizeof(head)); } int main() { //freopen("in.txt","r",stdin); int T,i,n,m,u,v,flag; LL w,ans,pri[N]; scanf("%d",&T); while(T--) { flag=1; ans=0; init(); scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%I64d",&pri[i]); for(i=1;i<=m;i++) { scanf("%d%d%I64d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } dijkstra(n,1); for(i=1;i<=n;i++) if(dis[i]==INF) { flag=0; break; } if(!flag) printf("No Answer\n"); else { for(i=1;i<=n;i++) ans+=pri[i]*dis[i]; printf("%I64d\n",ans); } } return 0; }
二.变形题
POJ 1797 Heavy Transportation
# include<cstdio> # include<cstring> # include<algorithm> using namespace std; # define N 1005 # define M 1000005 int num,head[N]; int n,m; int vis[N]; struct edge { int u,v,w,next; }e[M]; void addedge(int u,int v,int w) { e[num].u=u; e[num].v=v; e[num].w=w; e[num].next=head[u]; head[u]=num++; } int dfs(int u,int limit) { int i,v; vis[u]=1; if(u==n) return 1; for(i=head[u];i!=-1;i=e[i].next) { v=e[i].v; if(!vis[v]&&e[i].w>=limit) { if(dfs(v,limit)) return 1; } } return 0; } int pass(int limit) { memset(vis,0,sizeof(vis)); if(dfs(1,limit)) return 1; return 0; } int bin(int l,int r) { int m; while(l<=r) { m=(l+r)>>1; if(pass(m)) l=m+1; else r=m-1; } return r; } void init() { num=0; memset(head,-1,sizeof(head)); } int main() { // freopen("in.txt","r",stdin); int cas,T,i,u,v,w; scanf("%d",&T); for(cas=1;cas<=T;cas++) { init(); scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } printf("Scenario #%d:\n",cas); printf("%d\n\n",bin(0,1000000)); } return 0; }
# include<cstdio> # include<cstring> # include<map> # include<queue> # include<vector> # include<algorithm> using namespace std; typedef pair<int,int> PII; # define N 1005 # define M 1000005 priority_queue< PII,vector<PII>,less<PII> > q; //pair<dis,u> dis从大到小 int num,head[N]; int dis[N]; struct edge { int u,v,w,next; }e[M]; void addedge(int u,int v,int w) { e[num].u=u; e[num].v=v; e[num].w=w; e[num].next=head[u]; head[u]=num++; } void dijkstra(int n,int s) { int i,u,v; for(i=1;i<=n;i++) dis[i]=0; dis[s]=1<<30; q.push(PII(dis[s],s)); while(!q.empty()) { PII now=q.top(); u=now.second; q.pop(); if(now.first<dis[u]) continue; for(i=head[u];i!=-1;i=e[i].next) { v=e[i].v; if(dis[v]<min(dis[u],e[i].w)) { dis[v]=min(dis[u],e[i].w); q.push(PII(dis[v],v)); } } } } void init() { num=0; memset(head,-1,sizeof(head)); } int main() { //freopen("in.txt","r",stdin); int cas,T,i,n,m,u,v,w; scanf("%d",&T); for(cas=1;cas<=T;cas++) { init(); scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } dijkstra(n,1); printf("Scenario #%d:\n",cas); printf("%d\n\n",dis[n]); } return 0; }
POJ 2253 Frogger
# include<cstdio> # include<cstring> # include<cmath> # include<map> # include<queue> # include<vector> # include<algorithm> using namespace std; # define INF 1<<30 # define N 205 int vis[N]; double dis[N]; double mat[N][N]; struct point { double x,y; }p[N]; double calc(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 n,int s) { double mind; int i,j,u,v; dis[s]=0; for(i=1;i<=n;i++) { mind=1<<30; for(j=1;j<=n;j++) if(!vis[j]&&dis[j]<mind) { mind=dis[j]; u=j; } vis[u]=1; for(v=1;v<=n;v++) if(!vis[v]&&dis[v]>max(dis[u],mat[u][v])) dis[v]=max(dis[u],mat[u][v]); } } void init(int n) { int i,j; for(i=1;i<=n;i++) { vis[i]=0; dis[i]=INF; for(j=1;j<=n;j++) mat[i][j]=INF; } } int main() { // freopen("in.txt","r",stdin); int i,j,n,cas=1; while(scanf("%d",&n)!=EOF&&n) { init(n); for(i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) mat[i][j]=mat[j][i]=calc(p[i],p[j]); dijkstra(n,1); printf("Scenario #%d\n",cas++); printf("Frog Distance = %.3lf\n\n",dis[2]); } return 0; }
将这2题放在一起讲(2题都可用2分解)，我们可以利用Dijkstra特殊的结构解决一类问题----单调路径(况且这么叫),所谓单调路径，即为对于任何一条路径, 我们所求的值只会成单调变化
拿POJ1797来说,每经过一条路径,weight的值只会减少(甚至不变)，不会增加,看下图(边权值表示 weight,红色顶点为起点，绿色为终点,顶点下数字表示从起始点到达该顶点的weight值)
我们可以发现weight呈现非递增,而我们要求的则是weight的最大值,也就是说我们求的和它的趋势相反都可用Dijkstra来题解(请看下图),这跟Dijkstra可用heap优化是异曲同工(可以认真理解证明)
如果所求值和趋势为同一走向则不能用Dijkstra求解(如最长路)
三.好题
POJ 3463 Sightseeing
3.个人心得
Dijkstra的变形和应用非常多,需要一定的时间和题量积累，但是只要能深入理解Dijkstra的贪心 策略以及他在单调路径上(况且这么叫)的作用，很多问题都会迎刃而解