首页
登录 | 注册

图论最短路径算法(二)Dijkstra算法(迪杰斯特拉算法)

文章目录

      • 【初识】
      • 【算法描述】
      • 【算法分析&思想讲解】
      • 【算法图解】
      • 【应用场景】
        • 【例1】最短路径问题
        • 【例2】最小花费

【初识】

Dijkstra算法用来计算从一个点到其他所有点的最短路径的算法,是一种单源最短路径算法。也就是说,只能计算起点只有一个的情况。

Dijkstra的时间复杂度是O (N2),它不能处理存在负边权的情况。

【算法描述】

设起点为s,dis[v]表示从s到v的最短路径,pre[v]为v的前驱节点,用来输出路径。

a)初始化:dis[v]=∞(v≠s); dis[s]=0; pre[s]=0;

b)For (i = 1; i <= n ; i++)

  1. 在没有被访问过的点中找一个顶点u使得dis[u]是最小的。
  2. u标记为已确定最短路径
  3. For 与u相连的每个未确定最短路径的顶点v
    if (dis[u]+w[u][v] < dis[v])
    {
    dis[v] = dis[u] + w[u][v];
    pre[v] = u;
    }

c)算法结束:dis[v]为s到v的最短距离;pre[v]为v的前驱节点,用来输出路径。

【算法分析&思想讲解】

从起点到一个点的最短路径一定会经过至少一个“中转点”(例如下图1到5的最短路径,中转点是2。特殊地,我们认为起点1也是一个“中转点”)。显而易见,如果我们想求出起点到一个点的最短路径,那我们必然要先求出中转点的最短路径(例如我们必须先求出点2 的最短路径后,才能求出从起点到5的最短路径)。

换句话说,如果起点1到某一点V0的最短路径要经过中转点Vi,那么中转点Vi一定是先于V0被确定了最短路径的点。
图论最短路径算法(二)Dijkstra算法(迪杰斯特拉算法)

我们把点分为两类,一类是已确定最短路径的点,称为“白点”,另一类是未确定最短路径的点,称为“蓝点”。如果我们要求出一个点的最短路径,就是把这个点由蓝点变为白点。从起点到蓝点的最短路径上的中转点在这个时刻只能是白点。

Dijkstra的算法思想,就是一开始将起点到起点的距离标记为0,而后进行n次循环,每次找出一个到起点距离dis[u]最短的点u,将它从蓝点变为白点。随后枚举所有的蓝点vi,如果以此白点为中转到达蓝点vi的路径dis[u]+w[u][vi]更短的话,这将它作为vi的“更短路径”dis[vi](此时还不确定是不是vi的最短路径)。

就这样,我们每找到一个白点,就尝试着用它修改其他所有的蓝点。中转点先于终点变成白点,故每一个终点一定能够被它的最后一个中转点所修改,而求得最短路径。

【算法图解】

  • 算法开始时,作为起点的dis[1] = 0,其他的点dis[i] = 0x7fffffff。
    图论最短路径算法(二)Dijkstra算法(迪杰斯特拉算法)

  • 这时dis[2],dis[3],dis[4]被它的最后一个中转点1修改为了最短路径。
    图论最短路径算法(二)Dijkstra算法(迪杰斯特拉算法)

  • 这时dis[3],dis[5]被它们的最后一个中转点2修改为了最短路径。
    图论最短路径算法(二)Dijkstra算法(迪杰斯特拉算法)

  • 这时dis[4]也被它的最后一个中转点3修改为了最短路径。

  • 接下来的两轮循环将4、5也变成白点。N轮循环结束后,所有的点的最短路径即能求出。

【应用场景】

【例1】最短路径问题

【问题描述】
  平面上有n个点(n<=100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。
  
  若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离。现在的
  
  任务是找出从一点到另一点之间的最短路径。
  
【输入格式】
  输入,共n+m+3行,其中:
  
  第一行为整数n。
  
  第2行到第n+1行(共n行) ,每行两个整数x和y,描述了一个点的坐标。
  
  第n+2行为一个整数m,表示图中连线的个数。
  
  此后的m 行,每行描述一条连线,由两个整数i和j组成,表示第i个点和第j个点之间有连线。
  
  最后一行:两个整数s和t,分别表示源点和目标点。
  
【输出格式】
  输出,两行,一个实数(保留两位小数),表示从s到t的最短路径长度。
  另一行输出路径

【输入样例】
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5

【输出样例】
3.41
5<-2<-1

【实例代码】

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 1000;
int i,j,n,m,x,y,l,k;
double temp,minn,maxx;
int a[N][3],pre[N];
double w[N][N],dis[N];
bool b[N];

//求a,b之间的最短路径,以及打印路径 
void bfs(int a, int c){
	maxx = 0x7f;
	memset(dis,maxx,sizeof(dis));
	memset(pre,0,sizeof(pre));
	memset(b,1,sizeof(b));//用来标识图中的点是否被遍历,true代表蓝点,未遍历 

	//初始化起点相关数值 
	dis[a] = 0;
	b[a] = false; 
	pre[a] = 0;

	for(i=1; i<=n; i++){//起点能够直接相连的点赋值 
		dis[i] = w[a][i];
	}
	
	for(i=1; i<=n-1; i++){//寻找起点到剩余n-1个点的最短路径 
	
		minn = maxx;//minn是一个中间量,用来作为暂存最小值 
		l = 0;//用来记录中间路径
		for(j=1; j<=n; j++){//寻找合适的蓝点变成白点 
			if(b[j] && dis[j]<minn){
				minn = dis[j];
				l = j;
			} 
		}
		
		if(l == 0) break; //没有蓝点变成白点
		
		b[l] = false;//把蓝点变白 
		
		for(j=1; j<=n; j++){//更新由于新白点形成的dis
			 if(dis[l]+w[l][j]<dis[j]){
			 	dis[j] =  dis[l] + w[l][j];
			 	pre[j] = l;
			 }
		}
		
	}
	printf("%.2lf\n",dis[c]);
	
	//print path
	k = c;
	while(k!=0){
		cout<<k<<"<-";	
		k = pre[k];
	}
	cout<<a;
	 
}

int main(){
	cin>>n;
	for(i=1; i<=n; i++){
		cin>>a[i][1]>>a[i][2];
	}
	memset(w,0x7f,sizeof(w));
	cin>>m;
	for(i=1; i<=m; i++){
		cin>>x>>y;
		temp = sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2));
		w[x][y] = w[y][x] = temp;
	}
	cin>>i>>j;
	bfs(i,j);
	return 0;
}

【例2】最小花费

【问题描述】
在n个人中,某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费,请问A最少需要多少钱使得转账后B收到100元。

【输入格式】
第一行输入两个正整数n,m,分别表示总人数和可以互相转账的人的对数。

以下m行每行输入三个正整数x,y,z,表示标号为x的人和标号为y的人之间互相转账需要扣除z%的手续费 (z<100)。

最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账。

【输出格式】

输出A使得B到账100元最少需要的总费用。精确到小数点后8位。
【输入样例】

3 3
1 2 1
2 3 2
1 3 3
1 3
【输出样例】

103.07153164
【数据规模】

1<=n<=2000

【参考程序】

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 1000;
int i,j,n,m,x,y,l,k;
double temp,minn,maxx;
int a[N][4],pre[N];
double w[N][N],dis[N];//用来存储从起点到当前节点的最少钱数,初始化为0x7f 
int b[N];//表示是否遍历到 ,初始化=1,表示蓝点 

int main(){
	cin>>n>>m;
	maxx = 0x7f;
	memset(w,maxx,sizeof(w));
	for(i=1; i<=m; i++){
		cin>>x>>y;
		cin>>w[x][y];
	}
	
	cin>>x>>y;//输入起点和终点 
	
	memset(b,1,sizeof(b));
	memset(dis,0,sizeof(dis));
	memset(pre,0,sizeof(pre)); 
	dis[x] = 100;//假设起点的钱数=100
	
	for(i=1; i<n; i++){//至多遍历n-1次就可以 
		minn = 0;
		l = 0;
		for(j=1; j<=n; j++){
			if(b[j] && dis[j]>minn){
				minn = dis[j];
				l = j;
			}
		}
		if(l == 0) break;
		b[l] = 0;
		for(j=1; j<=n; j++){
			if(w[l][j]<maxx){//代表l,j之间有通路
				temp = 1-w[l][j]/100;//利率 
				if(dis[l]*temp > dis[j]){
					dis[j] = dis[l] * temp;
				}	
			}	
		}
	} 
	
	temp = 100*100/dis[y];
	printf("%.8lf\n",temp);
	
	return 0;
}


2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.010 s.
京ICP备10005923号