对于网图来说,最短路径,是指起始顶点到末尾顶点之间经过的边上权值之和最小的路径.

带权路径长度-----当图是带权图时,一条路径上所有边的权值之和,称为该路径的带权路径长度.

思路:Dijkstra算法,是指定一个源点,Dijkstra算法是求以固定源点到某一个点的路径长度,也就是计算从源点到某一个顶点的最小路径,每次找路径末尾顶点的邻接点中权值最小的,(不像生成树,找整个生成树距离其他顶点权值最小的,Dijkstra是找末尾顶点距离哪个不在路径中顶点的权值最小) 从末尾顶点找到的不在路径中的顶点的最小权值的边,将边连接的顶点P加入路径集合,之后查看加入新的顶点之后源点非路径中的顶点权值是否会减小,想计算到m顶点的权值,则让从源点经过p的权值, 再加上p到m的权值,就是源点到m的权值,用源点->p->m的权值和dist[m](表示还没加入顶点时候到m的权值)比较,如果这个权值小于dist[]数组中的,那就用这个权值更新dist[m], 并更改path[]数组,让path[m]=p;表示是经过p点到达m点.

dist[i]数组存放的是源点到各个顶点的权值,所以数组整体表示的是到每一个顶点的权值,因为Dijkstra算法思想就是从某一个源点出发,求到各个顶点的最小权值

dijkstra是有向图.如:

 现在要新加顶点3,  3->5的权值是   遍历dist[3]+arc[3][i]  和dist[i]进行比较,意思是现在新加入一个顶点3,计算源经过顶点3到其他顶点的权值,和未加入顶点3时,源点到其他顶点的权值进行比较.

一个S{}集合,是路径顶点集合,当有新顶点加入路径集合,则更新S集合                                            

一个U{}集合,当一个顶点加入生成树后,就将这个顶点从U{{}集合中删除                                       

一个dist[]数组,存放的是到各个顶点的最小权值,必须从固定源点开始,                                         

path[]数组,用源点v初始化path数组 ,表示一开始都是从源点v到达各个顶点的

Dijkstra算法思路:

1,定义一个S集合用于存放路径上的顶点,  定义一个U集合用于存放非路径中的顶点.                  

定义一个dist[]数组用于存放源点到各个顶点的权值。                                                                     

path[]用于存储是哪个顶点到哪个顶点,如path[3]=0,表示到达顶点3的最短边是通过顶点0到顶点3.

现在以顶点v=0为源点.( 将顶点v加入S(路径顶点数组)数组,并从U集合中删除v顶点);

1.用源点v初始化dist[]数组 , 和path[]数组,(将v顶点到所有顶点的权值初始化dist[]数组,当顶点v到顶点 i有边的时候,那么就将path[i] = v;表示v->i有边).

2.在dist[]数组中找到权值最小的一条边,此时到顶点1的权值最小为4,将顶点1加入到S集合中,*********,此时加入顶点1后到每一个顶点的权值与没加入顶点时候到所有顶点权值的大小,          此时顶点1加入,就遍历1到各个顶点的距离和为加入1时候到各个顶点的距离大小,发现未加入顶点1,到顶点2的权值是6,加入顶点1后,到顶点2的权值是0->1>2=5, 所以5<6,需要更新dist[]数组。并且更新path[]数组,path[2]=1;表示现在顶点1到顶点2的全累加和更小。上面步骤循环操作.  dist[]存放的是源点到各个顶点的最小权值,现在发现到顶点2的边权值最小,那么就去看比较之前到顶点2的权值和现在经过顶点1到顶点2的权值的大小.

dist[]数组方法: 现在将顶点1加入S,开始判断更小dist[]数组,去比较dist[2]和dist[1]+arc[i][j]因为arc[1][2]的权值为1,加上源点到1的权值,就是整个树到顶点2的权值和dist[]生成树到顶点2的权值作比较.

Dijskal算法得到的结果:

dist[]数组中存放这着到每个顶点的路径长度

path[]数组存放在从哪个顶点到哪个顶点,也就是路径.

代码实现:

Dijkstra算法首先自己要建立一个带权图


void Dijkstra(MGraph G,int startV){
	
	//初始化集合
	for(int i=0; i<G.vertexNum;  i++){
		dist[i]=G.arc[startV][i];
		
		if(dist[i]!= ∞){
			path[i] = startV;
		}else{
			path[i] = -1;     //如果源点到顶点 i没有边,那就将路径赋值为-1; 
		}
	}
	
	for(int i=0; i<G.vertexNum; i++){
		s[i] = 0;  //初始化集合S,初始化为0; 表示没有顶点加入,当s[i]=1, 表示顶点i加入路径集合
	}
	
	s[startV]=1;   //将源点放入集合S,1代表在S集合中, 0代表不在集合S中

	num = 1;  //num用来计算有多少个顶点加入到集合S中,因为startV已经加入了,所以i=1而不是i=0
	while(num<G.vertexNum){
		
		//在dist数组中查找s[i]为0 (说明元素不在生成树中的元素)的最小值权值元素 
		min = findMinDist(dist,s,G.vertexNum); 
		
		s[min]=1;  //将找到的邻接点加入生成树集合S
		
		for(int i=0; i<G.vertexNum; i++){
			if(s[i]==0 &&(dist[i]>dist[min]+G.arc[min][i])){
				dist[i] = dist[min] + G.arc[min][i];  //相加的权值替换原来的值
				path[i] = min;
			}
		}


        //打印最短路径信息  利用path[]数组的性质
        int j = min;
	    while(path[j]!=v){
		    vec.push_back(j);
		    j = path[j];
	    }
	    vec.push_back(j);
		
	    cout<<vertex[v];
	    while(!vec.empty()){
		    int x = vec.back();
		    vec.pop_back();
		    cout<<vertex[x];
	    }
	    cout<<" "<<dist[min]<<endl;


        num++;
 
	}	
	
}

查找dist[]数组中权值最小的索引(查找的是未加入S集合的元素)

const int INT_MAX = 66666;

int FindMinDist(int dist[],int s[],int vexnum) 
{
	int loc;
	int min=INT_MAX;
	for(int i=0;i<vexnum;i++)
	{
		if(s[i]==0)      //表示该顶点未加入S集合 
		{
			if(dist[i]<min)
			{
				min=dist[i];
				loc=i;
			}
		}
	}
	return loc;       //返回dist中最小元素的下标 
}

 打印最短路径信息:

    输出描述

    依次输出从编号为0的顶点开始的从小到大的所有最短路径,每条路径及其长度占一行。

    输入样例

    5 7
    A B C D E
    0 1 6
    0 2 2
    0 3 1
    1 2 4
    1 3 3
    2 4 6
    3 4 7


    输出样例

    AD 1
    AC 2
    AB 4
    ADE 8

转载版权:乐易云香港服务器 乐易云美国服务器

转载标题:Dijkstra算法(最短路径) 转载地址:https://www.123yun.com/article/2564.html

电脑服务器租用 rsyslog日志服务器 北斗时间服务器 服务器怎么租用

内容来源于网络如有侵权请私信删除