dijkstra.cpp

dijkstra算法的链表实现,另外需要include一个头文件,稍后上传

/******************************************************************************************************************************/
/*                                    实现寻找两点间最短带权路径的Dijkstra算法                                                */
/*                                  使用邻接矩阵表示带权图，并用链表储存矩阵数据                                              */  
/******************************************************************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "link_list.h"


float element(List *list,int row,int col);
int contd(List *D,int node);
float neardist(int *lastnode,List *adjacent,List *D,int i);
int allcontd(List *adjacent,List *D);
void quit();
void prtpath(List *path,int i,int sersp);
int searchlast(List *path,int i);
void showmsg();


void main()
{
	int i = 0,j,flag = 0,dim,sersp,lastnode = -1;
	float temp,least,temp1,temp2;
	char c = ' ';

	List adjacent;
	List D;
	List path;

	CreateList(&adjacent);
	CreateList(&D);
	CreateList(&path);
	FILE *fp;

	showmsg();

	if((fp = fopen("adjacent.dat","r")) == NULL)
	{
		printf("打开文件错误!\n");
		quit();
	}

	while (!feof(fp))                                                                                 //从文件读取邻接矩阵数据
	{
		fscanf(fp,"%f,",&temp);
		InsertList(temp,i++,&adjacent);
	}

	fclose(fp);

	for(j = 0;j * j <= i;j++)
		if (i == j * j)
			flag++;

	if(!flag)
	{
		printf("邻接矩阵必须是方阵，请重新输入!\n");
		quit();
	}
	
	dim = sqrt(i);
	flag=0;

	for(i = 0;i < dim - 1;i++)
		for(j = i + 1;j < dim;j++)
			if(GetList(i * dim + j,&adjacent)!=GetList(j * dim + i,&adjacent))
				flag++;

	if(flag)
	{
		printf("邻接矩阵必须是对称矩阵，请重新输入!\n");
		quit();
	}

	printf("输入源结点 P 的编号:\n");
	scanf("%d",&sersp);

	while(sersp > dim || sersp <= 0)
	{
		printf("超出范围，重新输入:\n");
		scanf("%d",&sersp);
	}

	sersp--;

	for(i = 0;i < dim;i++)
		InsertList((i == sersp)?0:(-1),i,&D);

	flag=0;

	while(!allcontd(&adjacent,&D))                                                                //寻找邻接到源点的最短路径长度
	{
		for(i = 0;i < dim;i++)
			if(!contd(&D,i))
			{
				temp1 = temp2;
				if((temp2 = neardist(&lastnode,&adjacent,&D,i)) == -2)
					temp2 = temp1;
				if(flag)
					temp2 = (temp1 < temp2) ? temp1 : temp2;
				if(neardist(&lastnode,&adjacent,&D,i) != -2)
					flag = 1;
			}
		if(flag)
		{
			least = temp2;
			flag = 0;
			for(j = 0;j < dim;j++)
			{
				if(neardist(&lastnode,&adjacent,&D,j) == least)
				{
					SetPosition(j,&D) -> entry = least;
					if(lastnode != -1)
					{
						InsertList(j,0,&path);
						InsertList(lastnode,0,&path);
					}
				}
			}
		}
	}

	for(i = 0;i < dim;i++)
		if(i != sersp)
		{
			if((int)GetList(i,&D) != -1)
			{
				printf("节点 %d 到节点 %d 的最短带权路径长度是: %g.\n",sersp + 1,i + 1,GetList(i,&D));
				prtpath(&path,i,sersp);
			}
			else
				printf("节点 %d 到节点 %d 没有路连接.\n",sersp + 1,i + 1);
		}

	quit();
}

/**********************************************返回邻接矩阵中某个元素的值*****************************************************/
float element(List *list,int row,int col)
{
	int dim;
	dim = sqrt(ListSize (list));
	return(GetList(row * dim + col,list));
}

/*******************************************判断给定的节点是否已邻接到源节点P*************************************************/
int contd(List *D,int node)
{
	return((int)GetList(node,D) >= 0);
}

/************************************计算给定节点到源节点P的最短路径，如果不存在那返回 -2 ************************************/
float neardist(int *lastnode,List *adjacent,List *D,int i)
{
	int dim,j,flag = 0;
	float temp1,temp2 = -2;
	dim = ListSize(D);
	*lastnode=-1;

	for(j = 0;j < dim;j++)
		if(contd(D,j))
			if((int)element(adjacent,i,j) != -1)
			{
				temp1 = temp2;
				temp2 = element(adjacent,i,j) + GetList(j,D);
				if(flag)
				{
					if (temp2 < temp1)
						*lastnode = j;
					temp2 = (temp1 < temp2) ? temp1 : temp2;
				}
				else
					*lastnode = j;
				flag = 1;
			}

	return temp2;
}

/***************************************判断是否所有能够连接的的节点都已连接到源节点P*****************************************/
int allcontd(List *adjacent,List *D)
{
	int i,flag = 0,lastnode;

	for(i = 0;i < ListSize(D);i++)
		if(!(contd(D,i)))
			if((int)neardist(&lastnode,adjacent,D,i) != -2)
			{
				flag = 1;
				break;
			}

	return !flag;
}

/***********************************************寻找源点P到已知节点经过的路径*************************************************/
void prtpath(List *path,int i,int sersp)
{
	int j = i;
	List way;
	CreateList(&way);
	InsertList(sersp,0,&way);
	while(searchlast(path,j) != sersp)
	{
		InsertList(searchlast(path,j),1,&way);
		j = searchlast(path,j);
	}
	printf("    路径是: %d",sersp + 1);
	for(j = 1;j < ListSize(&way);j++)
		printf(" -> %d",(int)GetList(j,&way) + 1);
	printf(" -> %d\n",i + 1);


}

/************************************************寻找已知结点的上一个节点***************************************************/
int searchlast(List *path,int i)
{
	int position;
	for(position = 1;position < ListSize(path);position += 2)
	{
		if(GetList(position,path) == i)
			break;
	}
	return (int)GetList(position - 1,path);
}

void quit()
{
	char c;
	while (c != '\n')
		c = getchar();
	c = getchar();
	exit(1);
}

void showmsg()
{
	printf("********本程序用Dijkstra算法寻找已知图中从源点P到其他各点的最短带权路径*********\n");
	printf("请将图的邻接矩阵输入文件adjacent.dat,用-1表示没有连接，然后执行程序.\n\n\n");
}