shortestpath.c

基于S3C44B0X开发的一个校园导航系统

///////////////////////////////////////////////////////////////////////////////
// Find shortest path function                                               //
///////////////////////////////////////////////////////////////////////////////
#include "ShortestPath.h"

BOOL shortestPath(Graph G, int v0, int vn, int* result, int* num)
{
	
		// 	*result保存确定的最短路径和长度
	int dist[MaxN];		// 保存从起点v0到达任意顶点的路径长度
	int path[MaxN][MaxN];		// path[u]存放从起点v0到达任意顶点的路径
	int s[MaxN];		// 保存最短路径已确定的顶点
	int i, j, u, w, m, n;
	int min;		// 当前的最短距离
	
	// 检测原点与目的点是否相同
	if (v0 == vn)
	{
     	result[0] = v0;
		result[1] = vn;
		(*num) = 3;
			
		return TRUE;
	}
	
	// 初始化path为-1
	for (m = 0; m < MaxN; m++)
	{
		for (n = 0; n < MaxN; n++)
		{
			path[m][n] = -1;
		}
	}
	
	for (i = 0; i < MaxN; ++i)
	{
		dist[i] = G.Arcs[v0][i];
		s[i] = 0;
		path[i][0] = v0;
	}
	
	path[v0][1] = v0;
	s[v0] = 1;
	dist[v0] = 0;
	
	for (i = 1; i < G.Vnum; i++)
	{
		min = INFINITY;
		u = v0;		// u 是从 v0 出发能够到达的所有顶点中路径最短者
		for (j = 0; j < G.Vnum; ++j)
		{
			if (s[j] == 0 && dist[j] < min)
			{
				min = dist[j];
				u = j;
			}
		}
		s[u] = 1;	// 找到 v0 到定点 u 的最短路径, 将顶点 u 加入集合 s
		for (w = 0; path[u][w] > -1 && w < G.Vnum; ++w);
		{
			// 记录 v0 到定点 u 的最短路径
		}
		if (path[u][w-1] != u)
		{
			path[u][w] = u;
		}
		
		// 如果到目的点最短路径已找到，则返回
		if (u == vn)
		{
			break;
		}
		
		for (j = 0; j < G.Vnum; ++j)
		{
			// 更新当前各顶点的最短路径及路径长度
			if (s[j] == 0 && (min+G.Arcs[u][j]) < dist[j])
			{
				dist[j] = min + G.Arcs[u][j];
				for (w = 0; w < G.Vnum; ++w)
					path[j][w] = path[u][w];
				for (w = 0; path[j][w] != -1 && w < G.Vnum; ++w);
				path[j][w] = j;
			}	// if //
		}
	} // for //

	// 最短路径经过的顶点数目
	(*num) = 0;
	for (i = 0; i < G.Vnum; i++)
	{
		if (path[vn][i] > -1)
		{
			(*num)++;
		}
	}

	// 将最短路径上的顶点和路径长度保存到result
	for (i = 0; i < (*num); i++)
	{
		result[i] = path[vn][i];
	}
	result[(*num)] = dist[vn];
	(*num) = (*num) + 1;
	
	return TRUE;	
}

//over