shortestdistance.cpp

C语言编写的Dijistra单源最短路径算法。有测试程序

/************************************************************************/
/*                     Dijkstra单源最短路径算法
/*  Writer:sailing    Date: 19/4/2008    基于 VC++6.0                                                       
/************************************************************************/


#include <stdio.h>
#include <stdlib.h>

#define MAX 1000               //1000表示一次无法到达 

//求单源最短路径的Dijskstra算法
void shortestDistance(int n, int v, int dist[], int prev[], int **c)
{
	bool s[MAX];
	int i, j;
	for(i = 0; i < n; i++)
	{
		dist[i] = c[v-1][i];
		s[i] = false;
		if(dist[i] == MAX)
			prev[i] = 0;
		else
			prev[i] = v;
	}
	dist[v-1] = 0;
	s[v-1] = true;

	for(i = 0; i < n - 1; i++)
	{
		int temp = MAX;
		int u = v;

		for(j = 0; j< n; j++)
		{
			if((!s[j] && (dist[j] < temp)))
			{
				u = j+1;
				temp = dist[j];                                    
			}
		}
		s[u-1] = true;
		for(j = 0; j < n; j++)
		{
			if ((!s[j]) && (c[u-1][j] < MAX))
			{
				int newdist = dist[u-1] + c[u-1][j];
				if(newdist < dist[j])
				{
					dist[j] = newdist;
					prev[j] = u;
				}
			}
		}
	}
}

int main()
{
	FILE *fp;
	char c;            //存储文件的第一个字符，代表有向图的点数
	int n;             //有向图的点数
	char **value;      //从文件获取有向图各边权的指针
	int **p;           //存储有向图各边权的指针
	int *dist;         //源点到其他点的距离
	int *prev;
	int i, j;

	//从文件中读取有向图的信息
	if((fp=fopen("1.txt", "r")) == NULL)
	{
		printf("Cannot open the file.\n");
		exit(1);
	}
	//读取有向图的点数
	c = fgetc(fp);
	n = c - '0';

	//为存储有向图信息的指针分配内存	
	value = (char **)malloc(sizeof(int *) *(n+1));
	p = (int **)malloc(sizeof(int *) *n);
	for(i = 0; i < n; i++)
	{
		p[i] = (int *)malloc(5*sizeof(int));
		value[i] = (char *)malloc(50*sizeof(char));
	}
	dist = (int*)malloc(n*sizeof(int));
	prev = (int*)malloc(n*sizeof(int));

	//读取换行符,避免少读'\n'造成读取数据错误
	fgetc(fp);

    //读取有向图各边的权
	for (i = 0; i < n; i++)
	{
		fgets(value[i], 50, fp);
	}
	//关闭文件
	fclose(fp);

	//初始化指针p
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < 5; j++)
		{
			*(*(p+i)+j) = 0;
		}
	}
	//将字符串中的字符转化成数字
	for(i = 0; i < n; i++)
	{
		int index = 0;
		int count = 0;       
			
		//将每个空格之前的字符串转化为数字, 存储至p内
		for(j = 0; j < 50; j++)
		{
			int t = 1;

			if(*(value[i] + j) == ' ')
			{
				int flag = j-1;

				while(index < j)
				{
					*(p[i] + count) += (*(value[i] + flag) - '0')*t;
					t *= 10;

					flag--;
					index++;
				}
				index = j + 1;
				count++;
			}
			if(*(value[i] + j) == '\n')
			{
				int strEnd = j -1;

				while(index < j)
				{
					*(p[i] + count) += (*(value[i] + strEnd) - '0')*t;
					t *= 10;
					
					strEnd--;
					index++;
				}
			}
		}
	}
	//计算从源顶点到其他顶点的最短距离,此测试的源顶点为1
	shortestDistance(n, 1, dist, prev, p);

	//输出源顶点到其他顶点的最短距离
	printf("the shortest distance from v1 to others:\n");
	for(i = 0; i < n; i++)
	{
		printf("1 to %d = %d.\n", i+1, dist[i]);
	}
	
	//输出从源到i的最短路径上每个顶点的前一个顶点
	for(i = 0; i < n; i++)
	{
		printf("prev[%d]:",i+1);
		printf("%d\n", prev[i]);
	}
	printf("\n");

	//释放分配的内存
	for(i = 0; i < n; i++)
	{
		free(p[i]);
		free(value[i]);
	}
	free(p);
	free(value);
	free(dist);
	free(prev);

	return 0;
}