最短路劲问题

2020 年 8 月 16 日
筆記
数据结构与算法, 最短路径

1.dijkstar算法（迪杰斯特拉算法）

dijkstar是用来计算图中单源最短路径问题，即算出从图中某一结点出发到其它结点的最短路径，也是基于贪心策略的算法。它每次选择图中的已经找到最小路径的顶点选择一条到达没有找到顶点的最小路径加入集合中。
dijkstar算法最的应用场所很多，比如在网络通信中，在网络层采用ospf协议进行ip数据包传输，每个路由器记录自己的到邻居的代价信息，这样可以把整个ospf区域网抽象成为一张图，采用dijkstar算法就可以找到代价最小的路由路径。

现在我们来看dijkstar算法是怎样执行的，下面是一个简单图结构，我们演示如何从v1找到其它顶点的最短路径。

上图的邻接矩阵为：

	1	2	3	4	5
1	0	10	∞	∞	5
2	∞	0	1	∞	2
3	∞	∞	0	4	∞
4	7	∞	6	0	∞
5	∞	3	9	2	0

dijkstar算法需要维护一个dist 和一个path数组，同时需要一个辅助数组set,具体用法请集合代码注释理解
算法开始初始化dist数组为矩阵的第一行，算法中用99999代替无穷大。初始化path的值为0；
初始化set数组的值为-1；

然后从dist中找到非零的最小值，并且判断最小值达到的顶点是否在集合s中，若在，则不加入s
，若不在则加入s，置s[i]的值为1表示加入。

然后根据新加入的顶点，判断有没有更小路径，然后更新dist和path数组

然后重复执行，知道所有顶点加入到了集合S中，求解过程如下

算法执行过程状态如下：

这里是代码：

//在这里，我们采用邻接矩阵的方式存储图

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

#define MAX 5
#define MAXCOST 99999 //最大权值 

typedef int Graph;

//打印数组信息 
void print_arr(string arr_name,int a[] ,int n){
	cout<<arr_name<<":[";
	for(int i=0;i<n;i++){
		if(i!=n-1){
			printf("%d,",a[i]);
		}else{
			printf("%d",a[i]);
		}
	}
	printf("]\n");
}

//dijkstar算法主体 
void dijkstar(Graph g[][MAX], int vertexNum, int v){
	int dist[vertexNum];  //储存v到各个顶点的最小权值; 
	int path[vertexNum];  //储存v到vi的最小路径是从哪个结点寻找的 如结点vi的是从path[i]到vi这条边加入的 
	int set[vertexNum];   //辅助数组，把已经寻找到的最短路径加入集合 

	int j=1;
	for(int i=0; i<vertexNum; i++){  //进行初始化操作 
		dist[i] = g[v][i];          //dist数组初始为v到各顶点的路径 
		path[i] = v;                //path初始为v 
		set[i] = -1;                //set初始为-1，表示为空 
	}
	set[v] = 1;       //表示v已经被找到  加入集合 
	while(j<vertexNum){	
		cout<<"--------------------------- "<<endl;
		cout<<"-------每次状态信息-------- "<<endl;
		print_arr("set",set,MAX);
		print_arr("dist", dist, MAX);
		print_arr("path", path, MAX);
		cout<<"--------------------------- "<<endl;
		
		int  min = MAXCOST-1;          //初始化min为最大权值，记录每次计算的最小路径值 
		int index = -1;                //index 记录每次 每次找到最小路径的点 
		for(int i = 0; i<vertexNum;i++){
			if(dist[i] !=0 && dist[i] < min && set[i] != 1 ){   //找到两个顶点不在同一集合的最小权值边 
				min = dist[i];
				index = i;	                           //记录 
			}
		}
		set[index] = 1;            //将找到的顶点加入集合 
		printf("v%d 到v%d 的最短距离为：%d\n",v,index,min);
		
		//每次加入了顶点就要更新路径信息 
		for(int i = 0; i<vertexNum;i++){
			if(dist[index]+g[index][i] < dist[i] && set[i] != 1){  
				dist[i] = dist[index]+g[index][i];    
				path[i] = index;
			}
		}
		j++;
	}
}		


int main(){
	Graph g[MAX][MAX] = {
		{0,10,MAXCOST,MAXCOST,5},
		{MAXCOST,0,1,MAXCOST,2},
		{MAXCOST,MAXCOST,0,4,MAXCOST},
		{7,MAXCOST,6,0,MAXCOST},
		{MAXCOST,3,9,2,0}
	};
	dijkstar(g,MAX,0);
	return 0;
}

1.Floyd算法（弗洛伊德算法）

floyd算法是用来求多源最短路径的算法，即在一个图中任意点到其他点的最短路径可以用floyd算法求出。Floyd是一个基于动态规划思想的算法，它的每一次迭代都是基于前一次的计算。
Floyd 算法的基本思想是：递推产生一个n 阶方阵序列A(-1)，A¹，A²，…..，A(k)。其中A(k)[i][j]表示从顶点vi到vj的路径长度，k表示绕行第k个顶点的运算步骤。初始时，A(-1)为图的邻接矩阵。以后再原路径加入顶点vk作为中间点。若增加中间定点后，得到路径比原来的路径更短，就更新方阵A(k)。

如对于有向图G,它的邻接矩阵如右图。

开始时，让A(-1)为邻接矩阵，然后进行一次迭代，将v0作为中间点，修改A(-1)称为A(0);
对于所有顶点，如有A[I][J]>A[i][0]+A[0][j],则将A[i][j]更新为A[i][0]+A[0][j]。一次类推进行迭代，由于图中只有三个顶点，只需要三次迭代就可以找到任意顶点到其它顶点的最短路径。三次迭代的结果为：

floyd的核心算法是：

void Floyd(Graph g){
	int A[MAX][MAX],path[MAX][MAX];//A记录每个顶点之间的最短路径值，path记录最短路径如何到达
	int i,j,k;
	for (i=0;i<G.n;i++){    //初始化操作 
		for (j=0;j<G.n;j++){
			A[i][j]=G.edges[i][j];
			path[i][j]=-1;
		}
	}
	for (k=0;k<G.n;k++){
		for (i=0;i<G.n;i++){
			for (j=0;j<G.n;j++){
				if (A[i][j]>A[i][k]+A[k][j]){//如果有更短的路径，则更新A,并且记录路径。
					A[i][j]=A[i][k]+A[k][j];
					path[i][j]=k;
				}
			}
		}
	}
}

Tags: 数据结构与算法最短路径