sh_path.c

该文件夹中包含了大部分经典的算法的源程序代码

/* file name: sh_path.c */
/*利用迪杰斯特拉算法去最短路径*/

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

#define MAX_V 100   /*最大节点数*/
#define VISITED 1
#define NOTVISITED 0
#define Infinite 1073741823

/* A[1..N][1..N] 为图的邻接矩阵 */
/* D[i] i=1..N 用来储存某起始顶点到i节点的最短距离 */
/* S[1..N] 用来记录顶点是否已经访问过 */
/* P[1..N] 用来记录最近经过的中间节点 */

long int A[MAX_V+1][MAX_V+1];
long int D[MAX_V+1];
long int S[MAX_V+1],P[MAX_V+1];
int source , sink , N;
int step = 1;

int top = -1;          /*堆栈指针*/
int Stack[MAX_V+1];   /*堆栈空间*/

void init();
int minD();
void output_step();
void output_path();
void Push(int);
int Pop();

void main()
{
	int t,I;

	init();
	output_step();

	for ( step =2;step <=N; step++ )
	{
		/* minD 传回一值t使得D[t] 为最小 */
		t = minD();
		S[t] = VISITED;
		/* 找出经过t点会使路径缩短的节点*/
		for ( I=1; I <= N; I++ )
		if ( (S[I] == NOTVISITED) && (D[t]+A[t][I] <= D[I]) )
		{
			D[I] = D[t] + A[t][I];
			P[I] = t;
		}
		output_step();
	}

	output_path();
}

void init()
{
	FILE *fptr;
	int i,j;
	long int weight;

	fptr = fopen("sh_path.dat","r");
	if ( fptr == NULL )
	{
		perror("sh_path.dat");
		exit(1);
	}

	fscanf(fptr,"%d",&N);       /*读取图节点数*/
	for ( i=1; i<=N; i++ )
		for ( j=1; j<=N; j++ )
			A[i][j] = Infinite; /*起始A[1..N][1..N]邻接矩阵*/
 
	while ( fscanf(fptr,"%d %d %ld",&i,&j,&weight) != EOF )
	A[i][j] = weight;       /*读取i节点到j节点的权weight */
	fclose(fptr);

	printf("Enter source node : ");
	scanf("%d",&source);
	printf("Enter sink node : ");
	scanf("%d",&sink);

	/* 起始各数组初值*/
	for ( i = 1; i <= N; i++ )
	{
		S[i] = NOTVISITED;  /*各顶点设为尚未访问*/             
		D[i] = A[source][i]; /*记录起始顶点至各顶点最短距离*/
		P[i] = source;       
	}
	S[source] = VISITED;   /*始起节点设为已经走访*/
	D[source] = 0;
}

int minD()
{
	int i,t;
	long int minimum = Infinite;

	for ( i=1;i<=N;i++ )
		if ( (S[i] == NOTVISITED) && D[i] < minimum )
		{
			minimum = D[i];
			t = i;
		}

	return t;
}

/* 显示目前的D数组与P数组状况 */
void output_step()
{
	int i;

	printf("\n Step #%d",step);
	printf("\n================================================\n");
	for ( i=1; i<=N; i++ )
		printf("  D[%d]",i);
	printf("\n");
	for ( i=1; i<=N; i++ )
		if ( D[i] == Infinite )
			printf("  ----");
		else
			printf("%6ld",D[i]);
	printf("\n================================================\n");
	for ( i=1; i<=N; i++ )
		printf("  P[%d]",i);
	printf("\n");
	for ( i=1; i<=N;i++ )
		printf("%6ld",P[i]);
}

/*显示最短路径*/
void output_path()
{
	int node = sink;

	/*判断是否起始顶点等于终点或无路径至终点*/  
	if ( (sink == source) || (D[sink] == Infinite) )
	{
		printf("\nNode %d has no Path to Node %d",source,sink);
		return;
	}

	printf("\n");
	printf(" The shortest  Path from V%d to V%d :",source,sink);
	printf("\n------------------------------------------\n");

	/*由终点开始将上一次经过的中间节点推入堆栈至到起始节点*/ 
	printf("  V%d",source);
	while ( node != source )
	{
		Push(node);
		node  = P[node];
	}
	while( node != sink)
	{
		node = Pop();
		printf(" --%ld-->",A[ P[node] ][node]);
		printf("V%d",node);
	}

	printf("\n Total length : %ld\n",D[sink]);
}

void Push(int value)
{
	if ( top >= MAX_V )
	{
		printf("Stack overflow!\n");
		exit(1);
	}
	else
		Stack[++top] = value;
}

int Pop()
{
	if ( top < 0 )
	{
		printf("Stack empty!\n");
		exit(1);
	}

	return Stack[top--];
}