单源最短路径.cpp

单源最短路径算法的C语言实现

#include<stdio.h>
#include<stdlib.h>
#define  MAX 20  //定义可输入的最多的结点数
typedef struct node {
	int index;//表结点的索引号
	node *next;
}Node;//定义链表中的结点结构
	
void path(int v,int **cost,int *dist,int n)//求最短路径长度的贪心算法实现函数
                                            //其中v表源结点，cost未图的成本矩阵，dist为存储最短路径
											//的数组，n表图的结点数目
{
	int s[MAX];//定义是否选取标志数组，注意此处用MAX而不能用参数n
	int temp[MAX];//此数组用于临时存储还未被选取的结点
	int sum,num,i,k,j,tempnum,min;
	Node *lu[MAX];//定义一个Node结构类型的指针数组，用于存放路径链的头结点
	              //,MAX是预定义的最大结点数
	Node *p,*q,*r;
	for(i=0;i<n;i++)
	{
		lu[i]=(Node *)malloc(sizeof(Node *));//为每个路径链的头结点分配内存空间
		p=(Node *)malloc(sizeof(Node *));//为生成的新结点分配内存空间
		p->index=v;
		p->next=NULL;
		lu[i]=p;
		q=(Node *)malloc(sizeof(Node *));//同上
		q->index=i;
		lu[i]->next=q;
		q->next=NULL;
	}	//初始化为每条路径链上由源点和终点两结点
	for(i=0;i<n;i++)
	{
		s[i]=0;
		dist[i]=cost[v][i];//初始化标志数组s以及dist
	}

	s[v]=1;//置待求结点为已选取结点
	dist[v]=0;//置待求结点到自身的最短路径为0
	for(num=1;num<n-1;num++)//循环执行n-1次确定由结点v出发的n-1条路
	{
		sum=0;//对temp数组中元素进行计数的变量
		for(j=0;j<n;j++)
		{
			if(s[j]==1)
				continue;
			else
			{
				temp[sum]=j;//temp数组中存放未被选取的结点的索引
				sum++;
			}
			
		}
		min=temp[0];
		for(i=0;i<sum;i++)
		{
			if(dist[temp[i]]<dist[min])
			{
				min=temp[i];
			}
		}//求出temp中所存放的未被选取的结点中使得dist[w]为最小的结点min
		s[min]=1;//置上步所获得的结点为已选取结点
		for(k=0;k<sum;k++)
		{
			tempnum=temp[k];
			if(tempnum==min)
			{
				continue;
			}
			if(dist[tempnum]>(dist[min]+cost[min][tempnum]))
			{
				dist[tempnum]=dist[min]+cost[min][tempnum];//修改dist[w]的值
				r=lu[min]->next;
				q=lu[tempnum];
				lu[tempnum]->next=NULL;
				while(r)
				{
					p=(Node *)malloc(sizeof(Node *));
					p->index=r->index;
					q->next=p;
					p->next=NULL;
					q=p;
					r=r->next;
				}//通过将min路径链上的结点拷贝到tempnum链上达到更新tempnum路径
				//链的目的
				p=(Node *)malloc(sizeof(Node *));
				p->index=tempnum;
				q->next=p;
				p->next=NULL;
			}//每修改一次dist[w]，就更新相应的路径链表
		}//对于所以未选取的结点，修改其对应的dist[w]，使其等于dist[w]和dist[u]+cost[min][w]
		//中最小的项
	}
	printf("\n**************sourse node is v%d****************",v);
	for(j=0;j<n;j++)
	{	
		if(dist[j]==0)
			continue;//单源结点到自身的最短路径不进行处理
		if(dist[j]>=2000)
			printf("\nthe shortest path of v%d--v%d :  没有路",v,j);//权值大于等于2000的转换为
		                                                            //没有路结果输出
		else
		{
			printf("\nthe shortest path of v%d--v%d :  %d",v,j,dist[j]);
			printf("\t最短路径序列为:");
			p=lu[j];
			while(p->next)
			{
				printf("v%d--",p->index);
				p=p->next;
			}
			printf("v%d",j);//输出单源最短路径序列
		}
	}//对存储最短路径的dist数组进行适当处理（主要针对两结点不存在路的情况即dist[i]值
	//大于等于预定义的大数2000），并且将存放最短路径序列的结点链转换输出为最短路径显示到屏幕
}
int main(void)
{
	int i;
	int j,n,var;
	int dist[MAX];
	int *cost[MAX];//定义指针数组用于存储成本矩阵，此处用指针主要用于将其作为path函数参数传进去
					//若用多维数组代替则会问题
	printf("please the number of node(n<20):");
	scanf("%d",&n);//输入待求解的有向图的结点数
	for(i=0;i<MAX;i++)
	{
		cost[i]=(int *)malloc(sizeof(int *));//为定义的指针数组分配内存空间
	}
	for(i=0;i<MAX;i++)
	{
		for(j=0;j<MAX;j++)
		{
			cost[i][j]=-1;//对cost初始化
		}
	}
	printf("\nplease input the matrix of the graph:(不存在的边将其权值置为2000)\n");
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			printf("\ncost[%d][%d]=",i,j);
			scanf("%d",&var);
			cost[i][j]=var;
		}//将待求解的有向图转化为成本矩阵并存储于cost中
	}
	printf("***********有向图邻接矩阵表示输出***********\n");
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			printf("%4d\t",cost[i][j]);
		}
		printf("\n");
	}//将输入的有向图矩阵显示出来
	for(i=0;i<n;i++)
	{
		path(i,cost,&dist[0],n);//调用贪心算法函数path求最短路径
		/*printf("\n**************sourse node is v%d****************",i);
		for(j=0;j<n;j++)
		{
			if(dist[j]>=2000)
				printf("\nthe shortest path of v%d--v%d :  没有路",i,j);
			else
				printf("\nthe shortest path of v%d--v%d :  %d",i,j,dist[j]);
		}*/ //对存储最短路径的dist数组进行适当处理（主要针对两结点不存在路的情况即dist[i]值
		//大于等于预定义的大数2000），然后输出结果
	}
}