地图最短路径算法

最短路径算法，做了堆优化有测试用例，可以随机生成地图，地图中的数字代表的是该点的高度，高度差为两点的距离

#include 
#include 
#include “heap.h“

#define  D_SIZE 33
#define	INFINITY	65535	//表示正无穷

int** make_dem（int size int roughness） {
	int seed = 12;//time（NULL）;
	srand（seed）;
	int** dem = malloc（size * sizeof *dem）;
	for （int x = 0; x < size; x++） {
		dem[x] = malloc（size * sizeof *dem[x]）;
		for （int y = 0; y < size; y++） {
			dem[x][y] = -1;
		}
	}
	int r = roughness;

	dem[0][0] =				50 - r / 2 + rand（） % r;  //产生数 50-r/2~50+r/2+1
	dem[size-1][0] =		50 - r / 2 + rand（） % r;
	dem[0][size-1] =		50 - r / 2 + rand（） % r;
	dem[size-1][size-1] =	50 - r / 2 + rand（） % r;

	for （int step = （size - 1）; step > 0; step /= 2） {
		r = r > 1 ? r / 2:r;
		if （r < 1） r = 1;
		for （int cx = 0; cx < （size-1） / step; cx++） {
			for （int cy = 0; cy < （size-1） / step; cy++） {
				int a = dem[cx*step][cy*step];
				int b = dem[cx*step+step][cy*step];
				int c = dem[cx*step][cy*step+step];
				int d = dem[cx*step+step][cy*step+step];

				dem[cx*step + step / 2][cy*step + step / 2] = （a + b + c + d） / 4 + rand（） % r - r/2;
				
				dem[cx*step + step / 2][cy*step]		= （a + b） / 2 + rand（） % r - r/2;
				dem[cx*step][cy*step + step / 2]		= （a + c） / 2 + rand（） % r - r/2;
				dem[cx*step + step][cy*step + step / 2] = （b + d） / 2 + rand（） % r-r/2;
				dem[cx*step + step/2][cy*step + step]	= （c + d） / 2 + rand（） % r-r/2;
			}
		}
	}
	for （int x = 0; x < size; x++） {
		for （int y = 0; y < size; y++） {
			dem[x][y] = dem[x][y]<0	? 0 : dem[x][y];
			dem[x][y] = dem[x][y]>99? 99: dem[x][y];
		}
	}
	return dem;
}

int cost_funcA（int diff） {
	int cost = 1;
	if （diff > 0） cost += diff * diff;
	return cost;
}

int cost_funcB（int diff） {
	int cost = 1;
	if （diff > 0）
		cost += diff * diff;
	else
		cost += diff;
	return cost;
}

void print_2D（int** array2D int size） {
	for （int x = 0; x < size; x++） {
		for （int y = 0; y < size; y++） {
			if （array2D[x][y] > 0） {
				printf（“%2d “ array2D[x][y]）;
			}
			else {
				printf（“（） “）;
			}
		}
		printf（“\n“）;
	}
}

void print_2D_ascii（int** array2D int size） {
	char *shades = “ .-:=+*#%@“;
	for （int x = 0; x < size; x++） {
		for （int y = 0; y < size; y++） {
			if （array2D[x][y] >= 0） {
				char shade = shades[array2D[x][y] * 10 / 100];
				printf（“%c%c“ shade shade）;
			} else {
				printf（“（）“）;
			}
		}
		printf（“\n“）;
	}
}

void creat_edge（int i int j int ** dem int dx int dy EdgeList * el Graph * adj_listchar fun）
{
	EdgeNodePtr ep = （EdgeNodePtr）malloc（sizeof（*ep））;
	ep->edge.to_vertex = （i + dx）*D_SIZE + j + dy;
	if （fun == ‘A‘）
		ep->edge.weight = cost_funcA（dem[i + dx][j + dy] - dem[i][j]）;
	else if （fun == ‘B‘）
		ep->edge.weight = cost_funcB（dem[i + dx][j + dy] - dem[i][j]）;
	ep->next = el->head;
	el->head = ep;
	++adj_list[i*D_SIZE + j].V;
}

void creat_adj_list（Graph * adj_list int ** demchar fun）
{//creat the adjacency list
	//建立结点信息
	for （int i = 0; i < D_SIZE; ++i）
	{
		for （i

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        7343  2018-05-24 15:32  dem.vcxproj
     文件        1147  2018-05-24 15:32  dem.vcxproj.filters
     文件         311  2018-05-24 15:32  graph.h
     文件        1397  2018-05-24 15:04  heap.h
     文件        8804  2018-05-26 10:36  main.c
     文件         164  2018-05-06 23:22  readme.txt
     文件       21928  2018-05-06 23:19  测试截图.png