迪杰斯特拉（Dijkstra）算法--有向网络最短路径

末蓝、 2022-04-18 06:54 364阅读 0赞

单源最短路径问题是：对于给定的有向网络G=（V，E）及单个源点v，求v到G的其余各顶点的最短路径。

## 算法的基本思想 ##

a.初始时，S只包含源点，即S＝\{v\}，v的距离为0。U包含除v外的其他顶点，即:U=\{其余顶点\}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。

b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

## 算法代码 ##

#include<stdio.h>
    #define max 1000                        //1000定义为最大值正无穷，表示两点之间不直接相通，或与自己相连接。
    #define n 100                           //n表示一个范围，需要大于图的顶点数目，以便定义一个数组储存。n的具体值根据情况而定。
    main()
    {
    	void DIJ(float C[n][n],int v);
    	int i,j,k,e,r;
    	float z;
    	float a[n][n];                       //定义一个足够大的数组，用于储存图的数据。
    	for(i=0;i<n;i++)
    	for(j=0;j<n;j++)
    	{
    		a[i][j]=max;                      //在正式写入数据之前，定义任意两点之间是不连通的，以便在后面为连通的数据单独赋值。
    	}
    	printf("请输入顶点数目和边数:");      //明确图中的节点数目和之间的边数。
    	scanf("%d%d",&r,&e);
    	printf("输入各边关系和权值:\n");
    	for(k=0;k<e;k++)                      //输入各边之间的连接点与权值。如1,2点之间的距离是10，应该输入“1 2 10”。
    	{
    		scanf("%d%d%f",&i,&j,&z);
    		a[i-1][j-1]=z;                    //只建立有向图用这句
    	}
    	printf("\n构造邻接矩阵:");
    	for(i=0;i<r;i++)                       //把图用邻接矩阵的形式输出。
    	{
    		printf("\n");
    		for(j=0;j<r;j++)
    		{
    			printf("%.1f\t",a[i][j]);
    		}
    	}
    	printf("\n");
    	printf("请输入起始点数字:");           //输入需要从某个节点开始。
    	scanf("%d",&i);
    	printf("\n距离\t路径");
    	DIJ(a,i);
    }
    void DIJ(float C[n][n],int v)                //Dijkstra算法
    {
    	float D[n];                              //用于储存起始点到其他各点间的距离
    	int P[n],S[n];                           //P[n]用数组储存当前点的前驱结点，S[n]表示已经取过的点集，代表红点集。
    	int i,j,k,v1,pre;
    	float min,inf=200;                       //inf一定要大于所有点间路径最大的数，这样才保证距离最大值的点能扩充到已经取好的点
    	v1=v-1;
    	for(i=0;i<n;i++)                        
    	{
    		D[i]=C[v1][i];                       //置初始距离值
    		if(D[i]!=max)                        //初始状态下各前驱结点。
    			P[i]=v;
    		else P[i]=0;                         //如果两点非连接定义其前驱为0
    	}
    	for(i=0;i<n;i++)                          
    		S[i]=0;                              //红点集开始是空集
    	S[v1]=1;                                 //初始点入红点集
    	D[v1]=0;                                 //设置初始点到自身的距离为0
    	for(i=0;i<n-1;i++)                       //扩充红点集
    	{
    		min=inf;                              
    		for(j=0;j<n;j++)                     
    			if((!S[j])&&(D[j]<min))
    			{
    				min=D[j];
    				k=j;
    			}
    			S[k]=1;							//在当前蓝点集中选取距离最小的顶点k+1，并加入红点集
    			for(j=0;j<n;j++)
    				if((!S[j])&&(D[j]>D[k]+C[k][j]))//调整各蓝点的间距值
    				{
    					D[j]=D[k]+C[k][j];         //修改蓝点j+1到红点集的距离
    					P[j]=k+1;                  //改变j+1的前驱为k+1
    				}
    	}										//所有顶点都扩充到S中
    	for(i=0;i<n;i++)
    	{
    		if(D[i]!=max)
    		printf("\n%.1f\t%d",D[i],i+1);        //打印两点间能连通的结果
    		pre=P[i];
    		while(pre!=0)							//用于继续找前驱结点
    		{
    			printf("<--%d",pre);
    			pre=P[pre-1];
    		}
    	}
    	printf("\n");
    }

以下图有向网络为例  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQzMDA5OTgy_size_16_color_FFFFFF_t_70]  
其邻接矩阵为  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQzMDA5OTgy_size_16_color_FFFFFF_t_70 1]  
先举个例子，求1到其它各点的最短路径。  
具体分析步骤如下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQzMDA5OTgy_size_16_color_FFFFFF_t_70 2]  
最后一行就是求得的结果。  
1->1=0。  
1->2=10:看最后一行，到达2的前驱是1。则输出1->2。  
1->3=50:到达3的前驱是4，到达4的前驱是1。则输出1->4->3。  
1->4=30:到达4的前驱是1。则输出1->4。  
1->5=60:到达5的前驱是3，到达3的前驱是4，到达4的前驱是1。则依次输出1->4->3->5。  
程序输出结果如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQzMDA5OTgy_size_16_color_FFFFFF_t_70 3]  
按照上图输入即可输出上述结果。  
以上是有向网络求最短路径，下面给出无向网络求最短路径的连接，感兴趣的可以看一下。[迪杰斯特拉（Dijkstra）算法–无向网络最短路径][Dijkstra]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQzMDA5OTgy_size_16_color_FFFFFF_t_70]: /images/20220418/2deff7d5fafe43cc97e48038cc5eb718.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQzMDA5OTgy_size_16_color_FFFFFF_t_70 1]: /images/20220418/ba08c52d74aa4defbd0c1466ac756ee0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQzMDA5OTgy_size_16_color_FFFFFF_t_70 2]: /images/20220418/e9e77f15aa204506bb31662cf8721bdf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQzMDA5OTgy_size_16_color_FFFFFF_t_70 3]: /images/20220418/433acad3c2c84a29a29abaf33785d61e.png
[Dijkstra]: https://blog.csdn.net/sinat_43009982/article/details/83933055