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

与有向网络不同的是，无向网络的邻接矩阵是对称的，所以在构造邻接矩阵的时候要注意。Dijkstra算法的具体内容参照我上次写的迪杰斯特拉（Dijstra）算法——有向网络最短路径

下面直接放代码和实例，以便更加理解使用。

#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;                    //只建立有向图用这句
		a[j-1][i-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");
}

有向网络和无向网络代码只有一行之差别，但是实际输出结果却大不相同。
下面以具体实例验证。
有向网络图

把上面的有向网络图改成无向网络图

邻接矩阵也发生变化

以4为源点，输出结果对比如下
有向网络输出结果：

无向网络输出结果：

由以上可以看出两次输出结果截然不同。

下面以另一个例子作为验证。

下面是一个无向网络

邻接矩阵在这里就不再给出。
以4为源点，输出结果如下

如果按照上图输入，就可以得到上图结果。